题目描述 给定M*N的矩阵，其中的每个元素都是-10到10之间的整数。你的任务是从左上角（1，1）走到右下角（M，N），每一步只能向右或向下，并且不能走出矩阵的范围。你所经过的方格里面的数字都必须被选取，请找出一条最合适的道路，使得在路上被选取的数字之和是尽可能小的正整数
分析 首先肯定要处理特例：第一行和第一列（处理为真或者1都行） 然后就是日常DP啦： [分两种处理：要上面的值或者左边的值，枚举可能的值（-1000~1000）] 最后从1开始一直搜f[n][m]，找到就输出然后退，-1这种特殊情况就不用我说了吧。。。
#include <iostream> #include <cstdio> int n,m,a[11][11],i,j,k; bool f[11][11][2002]; int main() { scanf("%d%d",&n,&m); for (i=1;i<=n;i++) for (j=1;j<=m;j++) scanf("%d",&a[i][j]); f[1][1][a[1][1]+1001]=true; for (j=2;j<=m;j++) for (k=1;k<=2001;k++) if (f[1][j-1][k]) f[1][j][k+a[1][j]]=true; for (i=2;i<=n;i++) for (k=1;k<=2001;k++) if (f[i-1][1][k]) f[i][1][k+a[i][1]]=true; for (i=2;i<=n;i++) for (j=2;j<=m;j++) { for (k=1;k<=2001;k++) if (f[i][j-1][k]) f[i][j][k+a[i][j]]=true; for (k=1;k<=2001;k++) if (f[i-1][j][k]) f[i][j][k+a[i][j]]=true; } for (k=1002;k<=2001;k++) if (f[n][m][k]) { printf("%d",k-1001); return 0; } printf("%d",-1); return 0; }