【每日算法Day 33】动态规划基础1
使用一维空间的动态规划题目，这些题目有除了动态规划以外的解法，但使用动态规划往往能显著降低时间复杂度。
# LeetCode 62. 不同路径 (opens new window)
# 题目描述
一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？
（1 <= m, n <= 100，题目数据保证答案小于等于 2 * 10 ^ 9）
# 示例
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
2
3
4
5
6
7
# 解题思路
设机器人坐标为(x,y)，显然当x=1或y=1的时候f(x,y)=1，当x、y都大于1时f(x,y)=f(x-1,y)+f(x,y-1)。则可以写出如下递归解法：
public int uniquePaths(int m, int n) {
if(m==1||n==1) return 1;
return uniquePaths(m-1,n)+uniquePaths(m,n-1);
}
2
3
4
不过该解法有很多重复的计算，会超出时间限制，因此使用一个O(m*n)的数组保存结果，即动态规划方法。
public int uniquePaths(int m, int n) {
if(m==1||n==1) return 1;
int[][] path=new int[m][n];
for (int i = 0; i < m; i++) {
path[i][0]=1;
}
for (int j = 0; j < n; j++) {
path[0][j]=1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
path[i][j]=path[i-1][j]+path[i][j-1];
}
}
return path[m-1][n-1];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
由于每次求f(x,y)只用到了f(x-1,y)和f(x,y-1)，因此考虑压缩使用的空间：使用O(n)的数组来保存单行的值（也可以是O(m)，选小的），我们一次填充一行的值。一开始该行全为1。从第二行开始，第1~n-1位置的值分别为前一个位置的值+当前位置的值，第0位永远为1。直到加到最后一行。
public int uniquePaths3(int m, int n) {
if(m==1||n==1) return 1;
int min=Math.min(m,n);
int max=Math.max(m,n);
int[] path=new int[min];
Arrays.fill(path,1);
for (int i = 1; i < max; i++) {
for (int j = 1; j < min; j++) {
path[j]=path[j]+path[j-1];
}
}
return path[min-1];
}
2
3
4
5
6
7
8
9
10
11
12
13
时间复杂度为O(m*n)，空间复杂度为O(min(m,n))。
# LeetCode 63. 不同路径 II (opens new window)
# 题目描述
在上一题的基础上，现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。
# 示例
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
2
3
4
5
6
7
8
9
10
11
12
# 解题思路
在上一题的基础上求值时，如果发现obstacleGrid(x-1,y)=1则结果不加上f(x-1,y)，如果发现obstacleGrid(x,y-1)=1则结果不加上f(x,y-1)。
另外这一题还有很多坑，如果起始点或者终止点有障碍那么返回0；初始化第一行（包括后面的第一列）时一旦发现有障碍，那么后面的部分就都不可达，对应的path值就为0。
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int y=obstacleGrid.length,x=obstacleGrid[0].length;
if (obstacleGrid[0][0]==1||obstacleGrid[y-1][x-1]==1) return 0;
int[] path=new int[x];
boolean flag=true;
for (int i = 0; i < x; i++) {
//初始化第一行一旦一次遇到障碍那么后面都不可达，为0
path[i]=(flag&&(flag=obstacleGrid[0][i]==0))?1:0;
}
flag=true;
for (int i = 1; i < y; i++) {
//每一行的头部（即第一列）一旦一次遇到障碍那么后面都不可达，为0
path[0]=(flag&&(flag=obstacleGrid[i][0]==0))?1:0;
for (int j = 1; j < x; j++) {
path[j]=obstacleGrid[i-1][j]==0?path[j]:0;
path[j]+=obstacleGrid[i][j-1]==0?path[j-1]:0;
}
}
return path[x-1];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
时空复杂度与上一题相同，看了下官方题解是直接把obstacleGrid用作DP数组来避免使用额外的O(n)空间，感觉有点犯规……
# LeetCode 120. 三角形最小路径和 (opens new window)
# 题目描述
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
# 示例
给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
2
3
4
5
6
7
8
# 解题思路
一开始看到这问题想到好像可以用回溯来做，DFS遍历到最底层时得到当前路径的和，利用一个全局变量比较并存储最小的路径。这种方法递归时传递的状态变量仅仅是一个O(1)大小的路径和，用到的空间是调用栈的大小，其大小就是三角形的行数n。
不过这样的时间复杂度会比较大，何况是在DP标签下的题目，那么可以尝试用O(n)的数组来保存到当前行各点上的最小路径和。自底向上求解问题。
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle==null||triangle.size()==0) return 0;
int n=triangle.size();
int[] total=new int[n];
for (int j = 0; j < n; j++) {
total[j]=triangle.get(n-1).get(j);
}
for (int i = n-2; i >=0 ;i--) {
//当前行为i，一共有i+1个点
for (int j = 0; j < i+1; j++) {
//得到i+1行对应相邻节点的最小值
int min=Math.min(total[j],total[j+1]);
total[j]=min+triangle.get(i).get(j);
}
}
return total[0];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18