【问题描述】
给定一个方形整数数组 A,我们想要得到通过 A 的下降路径的最小和。
下降路径可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
【输入形式】
第一行输入数组的大小n,第二行以后输入的n行分别是数组的第n行元素
【输出形式】
输出1行中含有一个数字,表示最短下降路径和。
【样例输入】
3
2 1 3
6 5 4
7 8 9
【样例输出】
13
【题解】
最短 下降路径
DP:1.状态表示
1.1集合:f[i][j] 从第1行到点(i,j)的下降路径和
1.2属性:Min
2.状态计算:f[i][j]可以由
min(f[i-1][j] , f[i-1][j-1], f[i-1][j+1]) + g[i][j]转移
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,g[N][N];
int f[N][N];
int main()
{
cin>>n;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
cin>>g[i][j];
//初始化
for(int j = 1 ; j <= n; j++)f[1][j] = g[1][j];
for(int i = 2 ; i <= n; i ++)
for(int j = 1 ; j <= n; j ++)
{
f[i][j] = f[i-1][j];
if(j-1>=1)f[i][j] = min(f[i][j],f[i-1][j-1]);
if(j+1<=n)f[i][j] = min(f[i][j],f[i-1][j+1]);
f[i][j] += g[i][j];
}
int res = 1e9;
for(int i = 1 ; i <= n ; i ++)
res = min(res,f[n][i]);
cout<<res;
return 0;
}