c++ 动态规划 (dp)
题目描述
观察下面的数塔. 写一个程序查找从最高点到底部任意位置结束的路径, 使路径经过数字的和最大.
每一步可以从当前点走到左下角的点, 也可以到达右下角的点.
输入
- 5
- 13
- 11 8
- 12 7 26
- 6 14 15 8
- 12 7 13 24 11
输出
86
AC 代码
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 505;
- int dp[MAXN][MAXN],a[MAXN][MAXN];
- int max(int a,int b)//max 函数求两个数字之间的最大值
- {
- return a>b?a:b;
- }
- int main()
- {
- int n;
- cin>> n;
- for (int i = 1;i <= n;i ++)// 输入
- {
- for (int j = 1;j <= i;j ++)
- {
- cin>> a[i][j];
- }
- }
- dp[1][1] = a[1][1];// 把起点直接放在 dp[] 里面
- 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];//dp 公式, 原理是先走一步, 然后扫描这个点的上一层的邻接点看看哪个点的 dp 值最大, 然后用最大值加上他本身
- }
- }
- int ans = 0;
- for (int i = 1;i <= n;i ++)
- {
- ans = max(ans,dp[n][i]);//ans 的作用是在最底部的元素中找一个最大的 dp, 输出
- }
- cout << ans << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3132548.html