动态规划路径问题

1.矩阵的最小路径和

程序员代码面试指南（第二版）

给定一个矩阵从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。
构造一个动态矩阵数组，当m，n大于0时，每次arr[i][j]选取上面与左面最小值加当前数组值。

	public static int minPath(int[][] arr) {
		int m = arr.length;
		int  n = arr[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (i == 0 && j >= 1)
					arr[0][j] += arr[0][j - 1];
				else if (i >= 1 && j == 0)
					arr[i][0] += arr[i - 1][0];
				else if (i > 0 && j > 0)
					arr[i][j] += Math.max(arr[i - 1][j], arr[i][j - 1]);
			}
		}
		return arr[m - 1][n - 1];
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.不同路径

Leetcode 62 ； medium；

一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。总共有多少条不同的路径？
初始先填充第一行和第一列，i=0或j=0到达只有直线一种走法，其余的点路径种类应为上面加左面的路径种类和。

	public int uniquePaths(int m, int n) {
		int[][] res = new int[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (i == 0)
					res[0][j] = 1;
				else if (j == 0)
					res[i][0] = 1;
				else
					res[i][j] = res[i - 1][j] + res[i][j - 1];
			}
		}
		return res[m - 1][n - 1];
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14