动态规划 ————数字三角形
题干
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中，从 7→3→8→7→5 的路径产生了最大
在上面的样例中，从 7→3→8→7→5 的路径产生了最大
输入格式
第一个行一个正整数 r ，表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行，包含那个可能得到的最大的和。
样例 #1
样例输入 #1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出 #1
30
提示
【数据范围】 对于 100% 的数据，1≤r≤10001≤r≤1000，所有输入在 [0,100] 范围内。
思路
分析数据，我们可以发现：
在此图中，我们可以发现路径的规律
1.对于第一列和最后一列的数，它们只会受到上一行同列的数的影响
2.除此以外，剩下的数字都会受到它上一行同列和前一列数字的影响
下附代码
代码
/**
* 本题考察点：线性dp
* 本人思路：手推状态转移方程 ,共r行，则有（r/2)*(ar+a1)个数
* step1:f[i][j]表示到第i行第j个数的最长距离
* step2:f[i][j] = max(f[i-1][j-1],f[i-1][j+1])+a[i][j]
* step3:在i==r时输出最大值
* 画图得到的规律：1.第一列的数，只受上一行这一列的数的影响
2.每行最后一列的数 ， 只受上一行前一列的书的影响；
3.除上述的两种情况外，其余数字受到上一行前一列和这一列的数字的影响
* 时间复杂度：(r*r)/2==5e5
* 空间复杂度：M即为数字的最多的个数（r=1000)
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+9;
const int M = 500510;
int f[N][1010];
int r;
int a[N][1010];
int main() {
cin>>r;
for(int i = 1 ; i <= r ; i++){
for(int j = 1;j<=i;j++){
cin>>a[i][j];
}
}
for(int i = 1 ; i <= r ; i++){
for(int j = 1 ; j <= r ; j++){
if(j==1){
f[i][j] = f[i-1][j] + a[i][j];
}else if(j==i){
f[i][j] = f[i-1][j-1] + a[i][j];
}else{
f[i][j] = max(f[i-1][j-1],f[i-1][j])+a[i][j];
}
}
}
int ans = 0;
for(int j = 1 ; j <= r ; j++){
ans = max(ans , f[r][j]);
}
cout<<ans;
return 0;
}
/**
* 至少5个不同类型的样例
* 样例1：小型
2
7
1 1
* 样例2：全部同样
5
7
7 7
7 7 7
7 7 7 7
7 7 7 7 7
* 样例3：全部斜着
10
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
* 样例4：全部直走
10
1000
1000 2
1000 2 3
1000 2 3 4
1000 2 3 4 5
1000 2 3 4 5 6
1000 2 3 4 5 6 7
1000 2 3 4 5 6 7 8
1000 2 3 4 5 6 7 8 9
1000 2 3 4 5 6 7 8 9 10
* 样例5：有直有斜
6
10
1 10
1 10 1
1 1 10 1
1 1 1 1 10
1 1 1 10 1 1
1 1 1 1 10 1 1
*
*/