| 动态规划2(数塔问题) | 您所在的位置：网站首页 › 写出相邻的数字宝宝怎么写的 › 动态规划2(数塔问题) |
动态规划2(数塔问题)
|
数塔问题是二维情况下动态规划的经典问题，下面以洛谷的一个例题来分析数塔问题以及动态规划：原题链接 题目描述 观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 输入格式 第一个行一个正整数 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 a[i][j]; cout for (int i = 1;i a[i][j]; for (int i = n;i >= 1;i--)//用i来表示行,且从最后一行开始 for (int j = 1;j int c; cin >> c; while (c--) { cin >> n; for (int i = 1;i a[i][j]; for (int i = n;i >= 1;i--)//用i来表示行,且从最后一行开始 for (int j = 1;j |
在上面的样例中,从7→3→8→7→5 的路径最大【本文地址】
公司简介
联系我们