动态规划（一）

这篇博客是动态规划的最入门的内容，具体的一些题目的练习留在后面的博客中来写，这里只介绍最基本的内容。

首先先引入一题例题：数字三角形（poj 1163）

题目描述：在上面的数字三角形中寻找一条从顶部到底部的路径，使路径上所经历的数字之和最大。路径上每一步只能往左下走，或者右下走。只需求出这个最大和即可，不必给出具体路径。

很明显啊这个三角形就是用二维数组来储存。

方法（一）：

#include 
#include 
using namespace std; 
#define MAX 101
int D[MAX][MAX];
int n;
int MaxSum (int i ,int j){
    //注意这个地方有两个参数，所以这个是用二维数组储存
     
    if(i == n){
        return D[i][j];
    }
    int x = MaxSum(i+1,j);
    int y = MaxSum(i+1,j+1);
    return max(x,y)+D[i][j];
}
int main(){
    int i,j;
    cin>>n;
    for(i = 1;i<=n;i++){
        for(j = 1;j<=i;j++){
            //这里循环控制了一下这样就是第二行输入2个这样下去
            cin>>D[i][j]; 
        }
    }
    cout<1,1)<<endl;
}

但是如果这个代码在poj上提交是没办法提交的，因为超时了，为什么超时呢？因为有大量的重复计算。

如果使用递归的方式深度遍历每条路径的话存在大量的重复计算，时间复杂度是O（2^n）。如果这个n是100的话肯定是超时的了。

对上面的方法进行一下改进，如果是因为重复计算二而导致的超时，我可不可以使用一个数组把计算一次的值用一个同样的二维数组来记住呢？这样的话就可以用n方的时间复杂度完成。因为三角形数字的总数是n*(n+1)/2。

#include 
#include 
using namespace std; 
#define MAX 101
int D[MAX][MAX];
int n;
int maxSum[MAX][MAX];
int MaxSum(int i,int j ){
    if(maxSum[i][j] != -1){
        return maxSum[i][j];
    }
    if(i == n){
        return D[i][j];
    }else{
        int x = MaxSum(i+1,j);
        int y = MaxSum(i+1,j+1);
        maxSum[i][j] = max(x,y)+D[i][j];
    }
}
int main(){
    int i,j;
    cin>>n;
    for(i = 1;i<=n;i++){
        for(j = 1;j<=i;j++){
            cin>>D[i][j];
            maxSum[i][j] = -1;
        }
    }
    cout<1,1)<<endl;
}

这个代码其实就是一开始把maxSum这个数组全部值给置成-1呗。在函数里面自己加上一个判断咯，如果是负1的话就没不必要算了直接返回相应的值就好了。（之前因为上学期的疏忽，对递归理解真的太浅了，所以现在经过痛苦的啃代码终于（^ - ^））.

再改进：

往往递归是有很大的局限性的，速度慢的同时还可能把栈给占满（很少发生）。所以一般来说我们就要做一件比较酷的事就是把递归转成递推（循环）。因为像这种题目用递归的思维就很好理解，但是用递推没法直接了解是怎么做的。

我现在把最后一层的内容先放到一个数组的最后一行里面。

用递推式不断的往上推，最上面的数其实就是这个和，这个数组的每一个位置都是相应位置到底边的最大和。这里说一下一步步推的过程，首先7是用2与4或者5里面大的相加，以此类推的往上走。

后面再进行一下空间的优化：

其实没必要用一个单独的二维数组来进行储存，只要用一维数组就好了，我可以把7直接存在4的位置。因为再算12的时候这个四已经没有用了。

这个是把第二层全部存于这个一位数组的结果。再来进一步来考虑的话其实都可以不需要这个一维数组，直接用D的最后一行就好了。

#include 
#include 
using namespace std; 
#define MAX 101
int D[MAX][MAX];
int n;
int *maxSum;
int main(){
    int i,j;
    for(i = 1;i<=n;i++){
        for(j = 1;j<=i;j++){
            cin>>D[i][j];
        }
    }
    maxSum = D[n];
    //注意这个循环是从倒数第二行开始的 
    for(i = n-1;i>=1;i--){
        for(j = 1;j<=i;j++){
            maxSum[j] = max(maxSum[j],maxSum[j+1])+D[i][j];
        }
    }
    cout<1]<<endl;
    return 0;
}

从这个例题入手后面来总结一下动态规划的一些解题的方法：

递归到动规的一般转化方法：

递归函数有n个参数，就定义一个n维的数组，比如上面递归函数有两个数组，那么就定义一个2维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始逐步填充数组，相当于计算递归函数值的逆过程。

递归到动规的一般解题过程：
1，将原问题分解为子问题：

把原问题分解为若干个小的子问题，子问题和原问题形式相同或者是类似，这只不过规模变小了。子问题都解决，原问题即解决了。子问题一旦求出就会被保存，所以每个子问题只需要解一次。举一个例子，比如说上面的数字三角形问题，子问题就是一个数正下方到底面最大和这个数右下方到地面最大。

2，确定状态：

在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值称之为一个“状态”。一个“状态”对应一个或多个子问题，所谓某个状态下的“值”，就是这个状态所对应子问题的解

这两段话可以再看看，我感觉虽然第一遍看很抽象但是如果对第一个例题有一个比较好的理解还是可以看懂的。

3，确定一些边界状态的值：

对于这个数字三角形而言的话，这个初始状态其实就是底边数字。

4，确定状态转移方程：

能用动规解决的问题的特点：

这里先用我的理解解释一下这些语句吧：最优子结构可以理解为数字三角形中一个子问题：就是一个数字的后面两个数字储存的也是到底下的最大值。无后效其实就是不用追究过程只要结果的感觉。所以这个也是为什么这个题目里面有提到只要结果不要路径。

算法与题目积累

动态规划（一）

相关

标签