/** * 有一个 M x N 的矩阵,其中每个格子里面都有特定的钱。 * 左上角走到右下角,只能向右或者向下走,问怎么走才能捡到最多的钱。 * 输出捡钱的路径。 * 解析: 动态规划。 首先找到子结构,构造递推式。 * 对于每个位置能捡到的最多的钱是: * a[i][j] = max{a[i-1][j] + w[i][j],a[i][j-1] + w[i][j]} */ #include <stdio.h> #define M 5 #define N 4 int w[M][N]; //矩阵 int a[M][N]; //当前捡到的最大的钱的值 int path[M][N]; //记录路径,1表示从上面捡着钱下来,0表示从左边捡着钱过来 void find_path(){ int i,j; a[0][0] = w[0][0]; //初始化左边界 for(i=0;i<M;i++){ a[i][0] = a[i-1][0] + w[i][0]; path[i][0] = 1; } //初始化右边界 for(j=0;j<N;j++){ a[0][j] = a[0][j-1] + w[0][j]; path[0][j] = 0; } //两个循环开始自底向上求解 for(i=1;i<M;i++){ for(j=1;j<N;j++){ int up = a[i-1][j] + w[i][j]; int left = a[i][j-1] + w[i][j]; if(up > left){ a[i][j] = up; path[i][j] = 1; } else{ a[i][j] = left; path[i][j] = 0; } } } } int main(){ int tmp[M][N] = {{4,3,12,1},{11,7,4,2},{6,20,15,2},{4,5,8,1},{3,3,4,6}}; int i,j; //初始化矩阵 for(i=0;i<M;i++) for(j=0;j<N;j++){ w[i][j] = tmp[i][j]; } printf("\n\n"); //自底向上求解 find_path(); //打印出路径以及每个位置能捡到的最多的钱数 for(i=0;i<M;i++){ for(j=0;j<N;j++) printf("%5d(%d)",a[i][j],path[i][j]); printf("\n"); } return 0; }
运行结果: