动态规划(1):数塔问题
题目
一些数字排成数塔的形状,其中第一层有一个数字,第二层有两个数字… 第n 层有n 个数字。现在要从第一层走到第n 层,每次只能走向下一层连接的两个数字中的一个,问:最后将路径上所有数字相加后得到的和最大是多少?
样例
5
5
8 3
12 7 16
4 10 11 6
9 5 3 9 4
题解
最优子结构:从5开始到结尾的最大和一定包含从8或者从3到结尾的最大和
重叠子问题:求8到结尾的,和从3到结尾的最大和都会用到从7到结尾的最大和
状态转移方程:
dp[n][j]=f[n][j];
dp[i][j]=max( dp[i+1][j],dp[i+1][j+1] )+f[i][j];
最优解:d[1][1]
C++代码
#include<cstdio>
#include"algorithm"
#include<iostream>
using namespace std;
#define N 100
int main(){
int f[N][N],dp[N][N];//dp[i][j]表示从第i行j列的数开始到结尾的最大
int n;
cin>>n;
//输入数塔
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
cin>>f[i][j];
}
//边界
for(int j=1;j<=n;j++)
{
dp[n][j]=f[n][j];
}
for(int i=n-1;i>=1;i--)
for(int j=1;j<=i;j++)
{
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
}
cout<<dp[1][1];
}