题解 P1130 【红牌】
引领天下
2017-10-25 19:58:38
纪念一下我做出的第一道DP题
此题很像数字三角形，只不过那题要求所经数值最大，这题最小。
~~ 话说我觉得并没有什么方程…… ~~
思路：从倒数第2步考虑，取两种方案中最小的一种，然后一直做到第一步，找最小值。
代码：
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;
int n,m,a[2005][2005],ans=1<<30;//ans必须要定大，不然找不到最小值
int main(){
scanf ("%d%d",&n,&m);
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)scanf ("%d",&a[i][j]);
for (int j=n-2;j>=0;j--)//从倒数第2步开始，向第一步推进
//我用的是0下标
for (int i=0;i<m;i++)
a[i][j]=min(a[(i+1)%m][j+1],a[i][j+1])+a[i][j];//取最小值，更新为之后的步骤的最小值
for (int i=0;i<m;i++)ans=min(ans,a[i][0]);//找答案
printf ("%d",ans);//结束
return 0;
}
```