题目
leetcode # 64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
分析
dp问题， f(m,n)表示走到坐标(m,n)的最大路径和，v[i][j]表示坐标(i,j)上的数字
因为到达坐标(m,n)只能从上方(m-1,n)或者左边(m,n-1)过来，所以$f(m,n)=max{f(m-1,n), f(m,n-1)}$
ok， 我们得到了状态转移方程式，
现在看下边界情况，f(i,j) 当i=0时，只有一种方案就是从左到右，所以f(0,j)只能等于f(0,j-1)+v[0][j-1],
同理f(i,j) 当j=0时，只有一种方案就是从上到下，所以f(i,0)只能等于f(i-1,0)+v[i][0];
其中f(0,0)等于v[0][0];
ok, let’s go!
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static int uniquePaths(int[][] v) {
int[][] f = new int[v.length][v[0].length];
f[0][0] = v[0][0];
// 当j==0
for (int i = 1; i < v.length; i++) {
f[i][0] = f[i - 1][0] + v[i][0];
}
// 当i==0
for (int j = 1; j < v[0].length; j++) {
f[0][j] = f[0][j - 1] + v[0][j];
}
for (int i = 1; i < v.length; i++) {
for (int j = 1; j < v[0].length; j++) {
f[i][j] = Math.min(f[i][j - 1], f[i - 1][j]) + v[i][j];
}
}
return f[v.length - 1][v[0].length - 1];
}
|
优化
按照上述代码执行，空间复杂度为o(n*m)，其实可以优化达到o(min(m,n))
每一个格子的最优解是min(上，左)+v(自己)，当i=0或者j=0时，子函数的最优解是确定的。
也就是上述的f(0,1),f(0,2),f(0,3)最优解都是确定的。f(1,0),f(2,0),f(3,0)也是确定的,如下图
假设m<n也就是行数小于列数， 我们构建数组f[m]=第一行的最优解列表，遍历到第二行我们可以得到(1,0),(1,1)和(1,2)的最优解再赋值到f[m]
数组，如下，
依次类推我们只需要一个数组就可以解决。
优化后的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
/**
* 空间优化后的不同路径(假设列数小于行数)
*
* @param v
* @return
*/
public static int uniquePaths(int[][] v) {
int[] f = new int[v[0].length];
f[0] = v[0][0];
// 初始化第一行的最优解
for (int j = 1; j < v[0].length; j++) {
f[j] = f[j - 1] + v[0][j];
}
// 从上往下从左往右处理每一个坐标的最优解
for (int i = 1; i < v.length; i++) {
// 当前行最左边的最优解 f[0]已被滚动更新，f[1]和f[2]还是上一行的最优解
f[0] = f[0] + v[i][0];
for (int j = 1; j < v[0].length; j++) {
// 滚动更新当前行的最优解, f[j-1]表示当前位置的左边最优解，f[j]表示当前位置的上方最优解
f[j] = Math.min(f[j], f[j - 1]) + v[i][j];
}
}
// 更新到最后一行,f数组的最后一个元素就是右下角坐标的最优解也就是最小和
return f[v[0].length - 1];
}
|
假设
依次类推我们只需要一个数组就可以解决。