动态规划的递推写法--状态转移方程

发布于 / 数据结构与算法 / Comments Off on 动态规划的递推写法--状态转移方程

我们先看一个图片:

这是一个经典问题,图片上的东东是"数塔"。第一层有一个数字,第二层有两个数字。。。以此类推。

问题是,如果从第一层走到第n层(当然,不能走回头路),路径上的数字相加的最大和是多少呢?

如果从上到下考虑,可能并不是特别好分辨。13下面的路径有11和8,应当选比较大的11,而8下面有26,要比11下面的12大出一倍......所以我们最好 使用从下到上的思想。

在介绍这个思想之前先想个办法把这些数字按照它的结构保存起来。我们使用矩阵来存储这些数字:

f[1][1] = 13;
f[2][1] = 11, f[2][2] = 8;
f[3][1] = 12, f[3][2] = 7, f[3][3] = 26;
......

接着我们从最下面的一层开始算,计算出每一个位置往下走所能收集到的最大数字之和。

第五行因为是最后一行,很显然往下走所能收集到的最大数字之和就是他们本身,我们将其保存起来

dp[5][1] = 12, dp[5][2] = 7, dp[5][3] = 13, dp[5][4] = 24, dp[5][5] = 11;

接着我们计算第四行。第四行往下走的时候需要加上第5行所能走到的最大数字,我们得到了

dp[4][1] = f[4][1] + max(dp[5][1], dp[5][2]) = 6 + 12;
dp[4][2] = f[4][2] + max(dp[5][2], dp[5][3]) = 14 + 13;
......

在第三行的计算中,我们同理,只需要加上每个数对应第四行所能达到的最大的数即可。这里不再敖述。

到了最后,计算到第一行,得到dp[1][1] = f[1][1] + max(dp[2][1], dp[2][2]);

这里dp[1][1]就是这里"从第一层走到第n层,路径上的数字相加最大"的结果了。

上面的算法中,每一次对当前位置的计算都是一次"决策",而dp[i][j]被称为问题的状态,上面计算dp[i][j]的式子称之为状态转移方程

下面根据上面的思想给出动态规划的完整代码:

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1000

int main(){
    int f[MAXN][MAXN];  //存放数塔
    int dp[MAXN][MAXN]; //存放状态

    int n;
    printf("请输入要计算到第几层:");
    scanf("%d", &n);
    printf("请输入数塔:\n");
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            scanf("%d", &f[i][j]);
        }
    }
    //计算最下面的一层
    for(int i = 1; i <= n; i++){
        dp[n][i] = f[n][i]; //最下面的一层dp都是自己本身
    }
    //从倒数第二层(n-1层)开始,向上计算dp[i][j]
    for(int i = n-1; i >= 1; i--){
        for(int j = 1; j <= i; j++){
            //状态转移方程
            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j];
        }
    }
    printf("%d\n", dp[1][1]);
    return 0;
}

输入前面提到的图中的数据,运行结果:

转载原创文章请注明,转载自: 斐斐のBlog » 动态规划的递推写法--状态转移方程
评论已关闭