动态规划求解矩阵累计和最大的路径

/**
* 有一个 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;
}

运行结果：