【算法浅析-0x01】动态规划算法浅析by arttnba3

0x00.绪论

动态规划（Dynamic Programming）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。同时也是各类信息学竞赛（ Olympiad in Informatics ）中较为常用的算法之一。

作为前·蒟蒻·OIer，对动态规划也是稍微了解一点点的XD，所以今天来简单地讲讲这个算法XD就当复习了

注：你一定想不到这篇文章拖了4个月才开始动笔2333333

0x01.什么是动态规划算法？

定义

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

维基百科：动态规划

简单而言：

动态规划便是通过寻找出一个问题的重叠子问题/最优子结构来优化对问题的求解，将问题进行分阶段求解，并确保当前阶段是过于所有阶段的完美总结。

适用于求解具有如下性质的问题

• 最优子结构： 无论其初始状态及初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态的过程而言，永远构成最优策略。这个原理的实质是多阶段决策过程具有这样的性质，即不管过去的过程如何，只从当前的状态和系统的最优化要求出发，作出下一步的最优决策 。
• 无后效性： 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性
• 子问题重叠： 动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间

如下图所示便是一个简单的动态规划算法的应用过程

求解过程

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。

动态规划-CSDN

适用于使用动态规划算法进行求解的问题的求解过程大致如下：

• 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

• 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

• 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

• 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

算法过程

递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。

动态规划-CSDN

在使用计算机求解适用于使用动态规划算法进行解决的问题时，我们首先需要确定动态规划三要素:

• 问题的阶段
• 每个阶段的状态
• 从前一个阶段转换到后一个阶段之间的递推关系

0x02.动态规划算法的简单应用

有了如上的这些概念，我们很容易就能知道该如何使用动态规划算法来解决实际生活（OI生活）中的问题

那么下面选几个OI中生活中常见的问题来简单讲讲动态规划23333

上楼梯问题

题目描述

楼梯有 NN 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

输入输出样例

输入 #1

4

输出 #1

5

说明/提示

• 对于 60% 的数据，N≤50；
• 对于 100% 的数据，N≤5000。

洛谷-P1255 数楼梯

问题分析

简单分析：

• 上0级楼梯：有0种走法

• 上1级楼梯：有1种走法：直接跨一阶楼梯

• 上2级楼梯：有2种走法：①先跨一阶再跨一阶；②直接跨两阶楼梯

• ……

• 上N阶楼梯：①先走到第N-1阶，再跨一阶楼梯②先走到N-2阶，再一步跨两阶楼梯：一共是F(N-1)+F(N-2)种走法

也就是说，我们走n级楼梯的走法数量都可以化为①先走到第N-1阶，再跨一阶楼梯②先走到N-2阶，再一步跨两阶楼梯的走法

状态转移方程

F(N) = F(N-1) + F(N-2)

有了这个方程之后，我们只需要知道走1级楼梯的走法数量与走2级楼梯的走法数量，就可以顺利地推出走任意一级楼梯的走法数量

时间复杂度

需要求解n次，故时间复杂度为线性时间复杂度O(N)

解决方案

构造代码如下：

# Python语言版
# Python的int是真的香，i了i了
a = 1
b = 2
n = int(input())
if n == 0:
    print(0)
elif n == a:
    print(a)
elif n == b:
    print(b)
else:
    for i in range(3,n+1):
        a,b = b,a+b
    print(b)

//C++版
//乱写的大数加法，将就着看⑧
#include <iostream>
#include <cstdlib>
using namespace std;

void add(int * num1, int * const num2)
{
    for(int i=0;num2[i]!=-1;i++)
    {
        num1[i]+=num2[i];
        if(num1[i+1]==-1)
        {
            num1[i+1] = 0;
            num1[i+2] = -1;
        }
        num1[i+1]+=num1[i]/10;
        num1[i]%=10;
    }
}

bool out(int * const num)
{
    if(*num!=-1)
    {
        bool flag = out(num+1);
        if(flag)
        if(*num == 0)
            return true;
        cout << *num;
        return false;
    }
    return true;
}

int main(void)
{
    int * n1,*n2,*temp;
    n1 = (int*)malloc(10000*sizeof(int));
    n2 = (int*)malloc(10000*sizeof(int));
    n1[0] = 1;n1[1]=-1;
    n2[0] = 2;n2[1]=-1;
    int n;
    cin >> n;
    if(n == 0)
        cout << 0;
    else if (n == 1)
        cout << 1;
    else if (n == 2)
        cout << 2;
    else
    {
        for(int i=2;i<n;i++)
        {
            temp = n1;
            n1 = n2;
            n2 = temp;
            add(n2,n1);
        }
        out(n2);
    }
    return 0;
}

最长上升降子序列问题

1759:最长上升子序列

• 总时间限制: 2000ms

• 内存限制: 65536kB

• 描述

一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。

• 输入

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

• 输出

最长上升子序列的长度。

• 样例输入

7 1 7 3 5 9 4 8

• 样例输出

4

• 来源

翻译自 Northeastern Europe 2002, Far-Eastern Subregion 的比赛试题

noi.openjudge.cn-1759：最长上升子序列

问题分析

最长上升子序列问题可以说是动态规划算法最经典的一个入门问题了，无论是在各大算法书上还是竞赛书上在讲到动态规划时往往会选择使用这个问题来入门

首先我们要求解最长上升子序列，我们就必须要将该序列上的各个结点“串起来”——对于任一结点都使用一个变量来储存在该结点上的最长上升子序列中该结点的下一结点的索引

其次，我们不难发现，对于任一结点与其往前所有结点构成的序列，要求解该序列中的最长上升子序列，我们只需要求解该最长上升子序列中的倒数第二个结点与往前所有结点所构成的序列、再接上该序列的最后一个结点即可

算法过程

状态转移方程

对于任一数字序列a₁,a₂,…,a_n，其最长上升子序列的长度为：f(a_n) = f(a_m)+1

• 其中a_m<=a_n

• f(a_m)为数字序列a₁,a₂,…,a_n-1所能构成的最大元素a_max不大于a_n的上升子序列中的最大长度

那么我们便可以使用遍历的方法逐一求出序列a₁，a₁、a₂，a₁、a₂、a₃，…，a₁、a₂、a₃、…、a_n中的最长上升子序列的长度

具体架构

状态转移方程构造出来后，接下来的代码就很好写了。

我们选择采用一个三维数组来储存结点信息

• 第一维：结点的值
• 第二维：结点上的最长上升子序列的长度
• 第三维：结点上的最长上升子序列中该结点的下一结点的索引

我们采用两层循环来对各个结点进行遍历:

• 第一层循环遍历每一个结点
• 第二层循环遍历初始节点到第一层循环结点的前一结点求解到该结点的最长上升子序列

时间复杂度

两层循环嵌套，我们很容易得出时间复杂度为O（n^2）

解决方案

构造代码如下：

#include <iostream>
using namespace std;
int main(void)
{
    int n, lis[1010][3]={0},_max = -1;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> lis[i][0];
        lis[i][1] = 1;
        lis[i][2] = i;
    }
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(lis[i][0]>lis[j][0])
            {
                //lis[i][1] = lis[i][1]>lis[j][1]+1?lis[i][1]:lis[j][1]+1,lis[i][2] = j;
                //it's too hard to understand, so I chose the following one to get it clear
                if(lis[i][1]<=lis[j][1]+1)
                {
                    lis[i][1] = lis[j][1]+1;
                    lis[i][2] = j;
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        _max = lis[i][1]>_max?lis[i][1]:_max;
    }
    cout << _max;
    return 0;
}

0 1 背包问题

咕了，下次接着更