DP问题大集合之一

发表于 | 分类于 | 阅读次数

description

  1. Unique Paths
    如下图所示：
    robot_maze
    从start的位置走，每次只能向下或者向右走，到达Finish的位置有多少种方法？
  2. Unique Paths II
    如果这些位置有些是不能走的（能走用0表示，不能走用1表示），那么又有多少种方法？
  3. Minimum Path Sum
    Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
  4. Climbing Stairs
    You are climbing a stair case. It takes n steps to reach to the top.
    Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
  5. House Robber
    英文比较啰嗦，小偷偷一排房屋，要求不能偷相邻的房屋。意思就是从给定的数组中选取元素，使得选取的元素和最大，要求不能选择相邻的元素。
  6. House Robber II
    这道题和上面一样，只不过房屋是一个环形的，也就是上面的情况首尾相连。

思路

[leetcode 62] Unique Paths

首先想到的当然是用DFS了，每次都有两种走法，向下和向右，而每次的这两种走法又都构成一个子问题，和start点的情况一样，这样便可以写出下面的代码：

1
2
3
4
5
6
7
8
9
10
//使用DFS做，但是不是有记忆的，这样会有很多重复的
public int uniquePaths(int m, int n) {
    return getUniquePathNum(m,n,1,1);
}
private int getUniquePathNum(int m, int n, int i, int j) {
    if(i==m&&j==n)return 1;
    if(i>m||j>n)return 0;
    return getUniquePathNum(m,n,i+1,j)+getUniquePathNum(m,n,i,j+1);
}

放到leetcode后，显示超时了，很显然会有很多重复的子问题，但是仍然当成第一次走；比如从start向右走一步后再向下走和从start向下走一步后再向右走一步都达到了相同的位置，这个位置就会重复计算；

这里我略掉有记忆的DFS，而是将递归变为for循环（自下向上变为自上向下）

以Finish为(0,0)点，用一个二维矩阵flag记录对应位置有多少种方法到达Finish点，有如下通项公式

这就叫动态规划

实质就是有记忆的DFS

代码如下：

1
2
3
4
5
6
7
8
9
10
11
//有记忆的遍历（DFS的反向）
public int uniquePaths(int m, int n) {
    int[][] flag=new int[m][n];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(i==0||j==0)flag[i][j]=1;
            else flag[i][j]=flag[i-1][j]+flag[i][j-1];
        }
    }
    return flag[m-1][n-1];
}

[leetcode 63] Unique Paths II

实质是一样的，只是需要多加几个条件，这里以Finish为(n,m)点，start为(0,0)点,如果obstacleGrid矩阵中对应的点为0，那么有:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
如果该位置是1直接返回0
否者如果该位置是最后一个位置，返回1
否者如果该位置在最下面一行，等于该位置右边那个位置
否者如果该位置在最右边一行，等于该位置下面的那个位置
否者等于该位置右边那个位置加上下面那个位置
 */
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int n=obstacleGrid.length;
    int m=obstacleGrid[0].length;
    int[][]flag=new int[n][m];
    for(int i=n-1;i>=0;i--){
        for(int j=m-1;j>=0;j--){
            if(obstacleGrid[i][j]==1)flag[i][j]=0;
            else if(i==n-1&&j==m-1)flag[i][j]=1;
            else if(i==n-1)flag[i][j]=flag[i][j+1];
            else if(j==m-1)flag[i][j]=flag[i+1][j];
            else flag[i][j]=flag[i+1][j]+flag[i][j+1];
        }
    }
    return flag[0][0];
}

[leetcode 64] Minimum Path Sum

同第二道:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int minPathSum(int[][] grid) {
    int n=grid.length;
    int m=grid[0].length;
    int [][] flag=new int[n][m];
    for (int i=n-1;i>=0;i--){
        for(int j=m-1;j>=0;j--){
            if(i==n-1&&j==m-1)flag[i][j]=grid[i][j];
            else if(i==n-1)flag[i][j]=grid[i][j]+flag[i][j+1];
            else if(j==m-1)flag[i][j]=grid[i][j]+flag[i+1][j];
            else flag[i][j]=grid[i][j]+Math.min(flag[i+1][j],flag[i][j+1]);
        }
    }
    return flag[0][0];
}

[leetcode 70] Climbing Stairs

这道跳台阶的题可以说是递归的经典题目，基本上一个递归就可以解决的：

1
2
3
4
5
public static int climbStairs(int n) {
    if(n==0)return 0;
    if(n==1)return 1;
    return climbStairs(n-1)+climbStairs(n-2);
}

但是这样的递归是很耗时的，因为有重复的，DP就是来拯救递归的：

代码如下：

1
2
3
4
5
6
7
8
9
public static int climbStairs(int n) {
    int [] dp=new int[n+1];
    for(int i=0;i<=n;i++){
        if(i==0)dp[i]=0;
        else if(i==1)dp[i]=1;
        else dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

[leetcode 198] House Robber

这道题使用一个2维数组，对于第i个元素有两种选择，一种是选取，一种是不选取；dp[0][i]表示不选取第i个元素，dp[1][i]表示选取第i个元素。不选取该元素的话，就取前面结果的最大值，选取该元素的话就要将没有选取该元素的最大值和当前元素相加，返回对最后一个元素分析后的两个结果中的最大值。【这道题的代码空间复杂度是可以优化的，因为我们不需要记录全部的值，见下面一道题】

1
2
3
4
5
6
7
8
9
public int rob(int[] nums) {
    int n=nums.length;
    int [][]dp=new int[2][n+1];
    for(int i=1;i<=n;i++){
        dp[0][i]=Math.max(dp[0][i-1],dp[1][i-1]);
        dp[1][i]=dp[0][i-1]+nums[i-1];
    }
    return Math.max(dp[0][n],dp[1][n]);
}

dp问题的难点在于构建dp矩阵，写通项公式。

[leetcode 213] House Robber II

前面一道题目使用dp的数组目的是为了更加的好理解，其实完全没有必要用数组的，如下面的代码，这道题无非就是上面题目的两种情况，一种是1到n-1，一种是2到n，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int rob(int[] num, int lo, int hi) {
    int include = 0, exclude = 0;
    for (int j = lo; j <= hi; j++) {
        int i = include, e = exclude;
        include = e + num[j];
        exclude = Math.max(e, i);
    }
    return Math.max(include, exclude);
}
public int rob(int[] nums) {
    if (nums.length == 1) return nums[0];
    return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
}

参考：Simple AC solution in Java in O(n) with explanation

如果觉得有帮助，给我打赏吧！