动态规划第二节课
文章目录
1.2 数塔问题
上一节课我们学习了最长上升子序列
今天我们来学习“大名鼎鼎”的数塔问题
数塔问题：要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
我们可以不关心之前是怎么走的
只关心走到一个点和走到另外一个点的最大和即可
！！！
!!!
!!!
这就是无后效性!
这就是无后效性!
这就是无后效性!
这就是无后效性!
这就是无后效性!
状态：
d
p
i
j
dp_{i\ j}
dpi j表示从起点走到第i行的第j列的最大和
d
p
i
j
=
max
(
d
p
i
−
1
j
,
d
p
i
−
1
j
−
1
)
+
a
i
j
dp_{ij}\space=\space\max(dp_{i-1\space j},\space dp_{i-1\space j-1}) + a_{ij}
dpij = max(dpi−1 j, dpi−1 j−1)+aij
这样就递推出来了 d p i j dp_{ij} dpij的值。
好了，来写一下代码
#include <iostream>
#include <cstdio>
using namespace std;
int a[1001][1001];
int dp[1001][1001];
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= i; j ++)
{
scanf("%d", &a[i][j]);
}
}
dp[1][1] = a[1][1];
for(int i = 2; i <= n; i ++)
{
for(int j = 1; j <= i; j ++)
{
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
}
}
int mx = a[n][1];
for(int i = 2; i <= n; i ++)
{
mx = max(mx, a[n][i]);
}
printf("%d\n", mx);
return 0;
}