c++ 动态规划(dp)
题目描述
观察下面的数塔。写一个程序查找从最高点到底部任意位置结束的路径，使路径经过数字的和最大。 每一步可以从当前点走到左下角的点，也可以到达右下角的点。
输入
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
输出
86
AC代码
#include
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;
}
另外一种方法
#include
#include
#include //STL库函数
using namespace std;
int main()
{
int t,n,dp[105][105],a[105][105];
cin >> t;//t组数据
while (t –)//重复执行直到t组数据都处理完
{
cin >> n;//塔的层数
for (int i = 1;i <= n;i ++)//输入
{
for (int j = 1;j <= i;j ++)
{
cin >> a[i][j];//把塔转化成数组
}
}
memset(dp,0,sizeof(dp));//把dp的值初始化为0
for (int i = 1;i <= n;i ++)//把a[]最后一行赋值到dp[],因为最后一行的dp[]就等于最后一行数本身
{
dp[n][i] = a[n][i];
}
for (int i = n – 1;i >= 1;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值最大，然后用最大值加上他本身,在把大的值选中
}
}
}
cout << dp[1][1] << endl;//输出
return 0;
}
原文出处：https://www.cnblogs.com/LJA001162/p/11234619.html