原题传送门
0.前言
显然,这是一道动态规划((DP))的入门题,也是一道非常经典的例题。
1.思路
(DP)和贪心主要就不同在:(DP)求全局最优解,贪心求局部最优解
这道题显然不是用贪心来做,因为当前的局部最优解可以不是全局最优解
(Solution 1) . 逆推
首先输入一个三角形样的三角形
for(int i=1;i<=R;i++){
for(int j=1;j<=i;j++){
read(a[i][j]);
}
}
因为是逆推,所以我们要先定义好(dp)数组里的最后一行的状态
for(int i=1;i<=R;i++){
dp[R][i]=a[R][i];
}
然后是最关键的一步,求出如下的状态转移方程:(dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);)
(dp[i][j])表示当前位置到最后一行的经过所有数的总和
(max(dp[i+1][j],dp[i+1][j+1]);) 指向左右两个方向取较大值
这里用加号的原因是逆推
放两张图来理解一下
输入的(a[][])数组
最后的(dp[][])数组
(Solution 2) . 顺推
逆推完了当然也可以顺推。思路大致与上无异。
依然输入一个三角形样的三角形
for(int i=1;i<=R;i++){
for(int j=1;j<=i;j++){
read(a[i][j]);
}
}
然后对三角形顶端的位置进行初始化
dp[1][1]=a[1][1];
接着还是这个关键的状态转移方程:(dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i-1][j-1]);)
思路和上面一样,只不过是顺推,要往来时路上面进行取最大值
不过有一点不一样:顺推推出来的结果最大值不确定,所以还需要找出结果:
int res=0;
for(int i=1;i<=R;i++){
for(int j=1;j<=i;j++){
res=max(res,dp[i][j]);
}
}
再放两张图
输入的(a[][])数组
最后的(dp[][])数组
2.代码
//逆推
#include<iostream>
#include<cstdio>
using namespace std;
inline void read(int &x){
int f=1;
char ch=getchar();
x=0;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
int R;
int a[1001][1001];
int dp[1001][1001];
int main(){
read(R);
for(int i=1;i<=R;i++){
for(int j=1;j<=i;j++){
read(a[i][j]);
}
}
for(int i=1;i<=R;i++){
dp[R][i]=a[R][i];
}
for(int i=R;i>=1;i--){ //从最后一行逆推
for(int j=1;j<=i;j++){
dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
}
}
printf("%d",dp[1][1]);
return 0;
}
//顺推
#include<iostream>
#include<cstdio>
using namespace std;
inline void read(int &x){
int f=1;
char ch=getchar();
x=0;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
int R;
int a[1001][1001];
int dp[1001][1001];
int main(){
read(R);
for(int i=1;i<=R;i++){
for(int j=1;j<=i;j++){
read(a[i][j]);
}
}
dp[1][1]=a[1][1];
for(int i=1;i<=R;i++){
for(int j=1;j<=i;j++){
dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i-1][j-1]);
}
}
int res=0;
for(int i=1;i<=R;i++){
for(int j=1;j<=i;j++){
res=max(res,dp[i][j]);
}
}
printf("%d",res);
return 0;
}