输入描述: 第一行包含一个正整数T(T<=10)，表示有T组测试数据。 每组数据第一行包含一个正整数n(3 <= n<=20）。 给定一个n*n矩阵图，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是花费和，返回所有路径中最小的花费和。 无摊位时花费为0，不会有负花费。 输出描述: 对于每一组数据，有一行输出，返回最小花费，最后输出无换行。 示例1 输入 1 5 25 81 51 98 43 19 10 36 81 91 95 38 7 84 40 87 27 72 9 30 33 81 68 21 71 输出 270
思路： 水题一道，找回感觉的第一题。直接简单dp就可。 a数组储存原方阵的数值，dp储存每个位置的最优值。每个位置的值可以是左边或者上边的数与此数相加得到，写出状态转移方程即可。
代码：
#include<bits/stdc++.h> using namespace std; const int N = 24; int a[N][N]; int dp[N][N]; const int INF=0x3f3f3f3f; int main() { int t; cin >> t; while(t--) { int k; cin >> k; for(int i = 1 ; i <= k ; i++) { for(int j = 1 ; j <= k ; j++) { cin >> a[i][j]; } } memset(dp,INF,sizeof(dp)); dp[1][1] = a[1][1]; for(int i = 1 ; i <= k ; i++) { for(int j = 1 ; j <= k ; j++) { dp[i][j]=min(dp[i][j],min(dp[i-1][j],dp[i][j-1])+a[i][j]); } } cout << dp[k][k] << endl; } return 0; }