动态规划2(数塔问题)
数塔问题是二维情况下动态规划的经典问题，下面以洛谷的一个例题来分析数塔问题以及动态规划：原题链接
题目描述
观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 在上面的样例中,从7→3→8→7→5 的路径最大
输入格式
第一个行一个正整数 rr ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行,包含那个可能得到的最大的和。
样例输入
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
样例输出
30
数据范围
对于100%的数据，1 ≤ r ≤ 1000，所有输入在 [0,100] 范围内。
数塔问题递归写法分析：
可以使用一个二维数组存储数塔，需要注意的是，在本题的数塔里，路径可以选择向左或者向右，但是若将数塔存储在二维数组中，数塔路径的选择只能是向下和向右下这两个方向在二维数组中，当前位置的下方是[i + 1][ j ]，右下方是[i +1][j + 1]本题样例中给出的是5层数塔，可以用dfs(1,1)表示从第1行第1列到第5行的最大路径，而想要找到答案，需要先寻找第2行到第5行的最大路径，即将5层数塔的最长路径转化为了4层数塔的最长路径这个子问题。即max{dfs(2,1),dfs(2,2)} + a[1][1]… … 以此类推当dfs()函数递归到最后1行(x == n)时，如数塔一共5行，目前正在执行dfs(5,1)，则直接返回数塔中的第5行第1列的数字a[5][1]即可，之后递归函数会依次向上继续返回
递归写法代码：
#include
#include
#include
#include
using namespace std;
const int N = 1010;
int a[N][N];//存储数据
int n;//递归函数中需要设置边界,故将n设为全局变量
int dfs(int x,int y)//x表示行,y表示列
{
if (x == n) return a[x][y];//递归边界
return max(dfs(x + 1,y),dfs(x + 1,y + 1)) + a[x][y];
}
int main()
{
cin >> n;
for (int i = 1;i <= n;i++)//读入数塔:数塔有n行
for (int j = 1;j <= i;j++)//每行有n列
cin >> a[i][j];
cout << dfs(1,1) << endl;//dfs(1,1):从第1行第1列到边界的最大路径
return 0;
}
当然，当数据范围很大时，由于递归写法的重叠子问题太多，所以又见到了熟悉的TLE… …话不多说直接上图 下面给出本题的AC代码：
#include
#include
#include
#include
using namespace std;
const int N = 1010;
int a[N][N];//存储数塔
int f[N][N];//表示从第i行第j列到第n行的最大路径
int n;
int main()
{
while (cin >> n)
{
for (int i = 1;i <= n;i++)
for (int j = 1;j <= i;j++)
cin >> a[i][j];
for (int i = n;i >= 1;i--)//用i来表示行,且从最后一行开始
for (int j = 1;j <= i;j++)//每行有i列,且从第一列开始
f[i][j] = max(f[i + 1][j],f[i + 1][j + 1]) + a[i][j];//自底向上计算最长路径
cout << f[1][1] << endl;//当for循环结束完毕之后f[1][1]:从数塔第1行第1列开始的最长路径
}
return 0;
}
动态规划的基本思想：将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。我们需要保存已解决的子问题的答案，这样可以避免大量的重复计算，节省时间。我们会用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中，而在需要时再找出已求得的答案。
换个新数塔哈~
如上图所示，若想找到这个8层数塔的最长路径，即将问题描述为：
从第一行第一列的数字7开始，找出一条最长路径。 很明显，若想解决上面的问题，有两条路径可以选择： ①从数字7下面的0开始寻找路径(子问题) ②从数字7右下的11开始寻找路径(子问题)
以此类推，不难发现，从红色位置开始找出一条最长路径，这个问题依赖于很多个子问题，而这些子问题构成了绿色部分。
我们只需要计算出①②两个子问题的答案，选择其中较大的值，再加上第一行第一列的那个数字，就可以得到数塔的最长路径。
由以上分析，得出状态转移方程：
dp[i][j] = max{dp[i + 1][j]，dp[i + 1][j + 1]} + a[i][j]
边界:当i > n时,f[i][j] = 0;
下面再给出数塔的一个例题 原题链接
AC代码：
#include
#include
#include
#include
using namespace std;
const int N = 1010;
int a[N][N];//存储数塔
int f[N][N];//表示从第i行第j列到第n行的最大路径
int n;
int main()
{
int c;
cin >> c;
while (c--)
{
cin >> n;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= i;j++)
cin >> a[i][j];
for (int i = n;i >= 1;i--)//用i来表示行,且从最后一行开始
for (int j = 1;j <= i;j++)//每行有i列,且从第一列开始
f[i][j] = max(f[i + 1][j],f[i + 1][j + 1]) + a[i][j];//自底向上计算最长路径
cout << f[1][1] << endl;//当for循环结束完毕之后f[1][1]:从数塔第一层开始的最长路径
}
return 0;
}