描述一个商人穿过一个正方形的网格，每经过网格上的一个点需要缴纳一定的费用。每行和每列上的点费用都是按照从小到大顺序排列的，并且对于每个网格上的点，其前后左右的各个点的收费都是不一样的。 编写程序设计一个商人总左上角走到右下角花费的最小费用。输入第一行是一个整数，表示正方行的宽度N (N <100), 后面n行n列为网格上每个点的费用输出一行，表示最小费用样例输入
5 1 4 6 8 10 2 5 7 15 17 6 8 9 18 20 10 11 12 19 21 20 23 25 29 33样例输出
109提示
可以用递归方法，或者动态规划方法
#include<string.h> #include<stdio.h> int n; int matrix[100][100]; int value[100][100]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int temp; scanf("%d", &temp); matrix[i][j] = temp; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if ((i == 0) && (j == 0)) { value[i][j] = matrix[i][j]; } else if ((i == 0) && (j != 0)) { value[i][j] = matrix[i][j] + value[i][j - 1]; } else if ((i != 0) && (j == 0)) { value[i][j] = matrix[i][j] + value[i - 1][j]; } else { int a = matrix[i][j] + value[i - 1][j]; int b = matrix[i][j] + value[i][j - 1]; value[i][j] = (a > b) ? b : a; } } } printf("%d", value[n - 1][n - 1]); return 0; }
