[Leetcode][DP]动态规划相关题目汇总/分析/总结

2019-07-17 本文已影响0人奔跑的程序媛A

Unified Dimensional
- 70 Climbing Stairs
- 91 Decode Ways
- 120 Triangle
- 139 Word Break
- 140 Word Break II
- 198 House Robber
- 213 House Robber II
- 279 Perfect Squares
- 263 Ugly Number
- 264 Ugly Number II
Two-dimensional
- 516 Longest Palindromic Subsequence
- 97 Interleaving String
- 62 Unique Paths
- 63 Unique Paths II
- 64 Minimum Path Sum
- 72 Edit Distance
- 10 Regular Expression Matching
- 221 Maximal Square
- 322 Coin Change
- 787 Cheapest Flights Within K Stops
- 1035 Uncrossed Lines
Three-dimensional
- 87 Scramble String
  980 Unique Paths III
- 741 Cherry Pickup

[Unified Dimensional]

#70 Climbing Stairs

Sol

    public int climbStairs(int n) {
        if(n <= 2) return n;
        int i1 = 1, i2 = 2;
        for(int i = 3; i <= n; i++){
            int tmp = i1;
            i1 = i2;
            i2 = tmp + i1;
        }
        return i2;
    }

#91 Decode Ways

Sol
case: 含有10

public int numDecodings(String s) {
        char[] ch = s.toCharArray();
        if(ch[0] == '0') return 0;
        if(ch.length < 2) return 1;
        int n = s.length();
        int i1 = 1, i2 = (ch[1] == 0 ? 0 : 1);
        int var = (ch[0]-'0') * 10 + (ch[1] - '0');
        if(var%10==0) i2 = 0;
        if(var >= 10 && var <= 26) i2++;
        for(int i = 2; i < n; i++){
            int tmp = (ch[i] == 0 ? 0 : i2);
            var = (ch[i-1]-'0') * 10 + (ch[i]-'0');
            if(var%10==0) tmp = 0;
            if(var >= 10 && var <= 26) tmp += i1;
            i1 = i2;
            i2 = tmp;
         }
        return i2;
    }

#120 Triangle

Sol Bottom-up

    public int minimumTotal(List<List<Integer>> triangle) {
        int row = triangle.size();
        int last_row_col = triangle.get(row-1).size();
        int[] dp = new int[last_row_col];
        for(int i = 0; i < last_row_col; i++){
            dp[i] = triangle.get(row-1).get(i);
        }
        for(int i = row-2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);
            }
        }
        return dp[0];
        
    }

#139 Word Break

Sol

    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++){
                String sub = s.substring(j, i);
                if(wordDict.contains(sub) && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

#140 Word Break II

Sol right-left

Map<Integer, List<String>> map; //index, res
    Set<String> dict;
    public List<String> wordBreak(String s, List<String> wordDict) {
        map = new HashMap<>();
        dict = new HashSet<>();
        for(String sh: wordDict) dict.add(sh);
        return help(s, s.length());
    }
    public List<String> help(String s, int end){
        List<String> res = new ArrayList<>();
        if(end == 0){
            res.add("");
            return res;
        }
        if(map.containsKey(end)) return map.get(end);
        for(int i = 0; i < end; i++){
            String sub = s.substring(i, end);
            if(dict.contains(sub)){
                List<String> next = help(s, i);
                for(String str: next){
                    res.add((str.length()==0)?sub : str + " " + sub);
                }
            }
        }
        map.put(end, res);
        return res;
    }

#198 House Robber

Sol

public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);
        int i1 = nums[0], i2 = Math.max(nums[0], nums[1]);
        int n = nums.length;
        for(int i = 2; i < n; i++){
            int tmp = Math.max(i1 + nums[i], i2);
            i1 = i2; 
            i2 = tmp;
        }
        return i2;
    }

#213 House Robber II

Sol

public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);
        int a = help(nums, 0, nums.length-1);
        int b = help(nums, 1, nums.length-1);
        return Math.max(a, b);
    }
    public int help(int[] nums, int s, int len) {
        if(len == 2) return Math.max(nums[s], nums[s+1]);
        int i1 = nums[s], i2 = Math.max(nums[s], nums[s+1]);
        for(int i = s+2; i < s+len; i++){
            int tmp = Math.max(i1 + nums[i], i2);
            i1 = i2; 
            i2 = tmp;
        }
        return i2;
    }

#279 Perfect Squares

Sol DP
dp[0] = {0} = 1
dp[1] = {1} = 1
dp[2] = {1, 1} = 2
dp[3] = {1, 1, 1} = 3
dp[4] = {4} = 1
dp[5] = {4, 1} = 2
dp[n] = Min(1+ dp[n - i * i]) for i * i <= n && i = 1,2...n

    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j*j <= i; j++){
                dp[i] = Math.min(dp[i], 1 + dp[i-j*j]);
            }
        }
        return dp[n];
    }

#263 Ugly Number

easy

Sol

public boolean isUgly(int num) {
        if(num <= 0) return false;
        if(num == 1)  return true;
        while(num % 2 == 0) num /= 2;
        while(num % 3 == 0) num /= 3;
        while(num % 5 == 0) num /= 5;
        return num == 1;
    }

#264 Ugly Number II

Sol
x=y=z=1; k=1
k is ugly number: k = 2x + 3y + 5z;
dp[++k] = min(2x, 3y, 5z)
更新xyz

public int nthUglyNumber(int n) {
        int p2 = 1, p3 = 1, p5 = 1;
        int[] dp = new int[n+1];
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = Math.min(Math.min(2 * dp[p2], 3 * dp[p3]), 5 * dp[p5]);
            if(dp[i] == 2 * dp[p2]) p2++;
            if(dp[i] == 3 * dp[p3]) p3++;
            if(dp[i] == 5 * dp[p5]) p5++;
        }
        return dp[n];
    }

[Two-dimensional]

#516 Longest Palindromic Subsequence

Sol
dp[i][j] denotes s[i...j] longest length of the Palindromic Subsequence.
base case: dp[i][i] = 1
if s.charAt(i) == s.charAt(j)
dp[i][j] = 2 + dp[i+1][j-1]
else dp[i][j] = max(dp[i + 1][j], dp[i][j-1])
return dp[0][len-1]

i 从后往前，j从i往后

public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for(int i = 0; i < n; i++) dp[i][i] = 1;
        for(int i = n-1; i >= 0; i--){
            for(int j = i+1; j < n; j++){
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = 2 + dp[i+1][j-1];
                else
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }

#97 Interleaving String

Sol
boolean dp[i][j] denotes whether s1[0..i] and s2[0...j] make the string s3[0..i+j]
base case:
dp[0][0] = T
dp[0][j] = (s2[j-1] == s3[i+j-1] && dp[0][j-1])
dp[i][0] = (s1[i-1] == s3[i+j-1] && dp[i-1][0])
Iterative:
if(s1[i] != s3[i+j] && s2[j] != s3[i+j]) return false
else if(s1[i-1] == s3[i+j-1]) dp[i][j] = dp[i-1][j]
else if(s2[j-1] == s3[i+j-1]) dp[i][j] = dp[i][j-1]

public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() != s1.length() + s2.length()) {
            return false;
        }
        int n1 = s1.length(), n2 = s2.length();
        boolean[][] dp = new boolean[n1+1][n2+1];
        //dp[0][0] = true;
        for(int i = 0; i <= n1; i++){
            for(int j = 0; j <= n2; j++){
                if(i == 0 && j == 0)
                    dp[0][0] = true;
                else if(i == 0)
                    dp[0][j] = dp[0][j-1] && s2.charAt(j-1) == s3.charAt(j-1);
                else if(j == 0)
                    dp[i][0] = dp[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1);
                else
                    dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i + j-1)
                    || dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i + j-1);
            }
        }
        return dp[n1][n2];
    }

#62 Unique Paths

Sol
dp[i][j] denotes the unique path from (0,0) to (i,j)
--base case:
dp[0][0] = 1;
dp[0][j] = 1;
dp[i][0] =1;
--Iterative:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
--return
dp[n-1][m-1]

    public int uniquePaths(int m, int n) {
        int[][] dp = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[n-1][m-1];
    }

#63 Unique Paths II

Sol
dp[i][j] denotes the unique path from (0,0) to (i,j)
--base case:
dp[0][0] = obstacleGrid[0][j] == 1 ? 0 : 1;
dp[0][j] = (obstacleGrid[0][j] == 1 ? 0 : dp[0][j-1]);
dp[i][0] = (obstacleGrid[i][0] == 1 ? 0 : dp[i-1][0]);
--Iterative:
dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1]
--return
dp[n-1][m-1]

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] dp = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(i==0 && j == 0) dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : 1;
                else if(i == 0) dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i][j-1];
                else if(j == 0) dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j];
                else dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[n-1][m-1];
    }

#64 Minimum Path Sum

Sol
dp[i][j] denotes the Minimum Path Sum from (0,0) to (i,j)
--base case:
dp[0][0] = grid[i][j];
dp[0][j] = dp[0][j-1] + grid[0][j];
dp[i][0] = dp[i-1][0] + + grid[i][0];
--Iterative:
dp[i][j] = Min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
--return
dp[n-1][m-1]

public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] dp = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(i==0 && j==0) dp[i][j] = grid[i][j];
                else if(i == 0) dp[i][j] = dp[0][j-1] + grid[0][j];
                else if(j == 0) dp[i][j] = dp[i-1][0] + grid[i][0];
                else dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[n-1][m-1];
    }

#72 Edit Distance

Sol
dp[i][j] denotes the edit distance from word1[0...i) and word2[0...j)
--base case:
dp[0][0] = 0;
dp[0][j] = j;
dp[i][0] = i;
--Iterative:
if(word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1]
else
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
--return
dp[n][m]

public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        int[][] dp = new int[n+1][m+1];
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= m; j++){
                if(i == 0) dp[i][j] = j;
                else if(j == 0) dp[i][j] = i;
                else if(word1.charAt(i-1) == word2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j]);
            }
        }
        return dp[n][m];
    }

#10 Regular Expression Matching

Sol
dp[i][j] denotes whether there is a Regular Expression Matching between s[i...) and word2[j...)
--base case:
dp[n][m] = true
--Iterative:
pre_check = word2[j] == word1[i] || word2[j] == "."
if(word2[j+1] != "*") dp[i][j] = pre_check && dp[i+1][j+1];
else dp[i][j] = pre_check && dp[i+1][j] || dp[i][j+2];
--return:
dp[0][0]

public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n+1][m+1];
        dp[n][m] = true;
        for(int i = n; i >= 0; i--){
            for(int j = m-1; j >= 0; j--){
                boolean pre = i < n && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                if(j+1 < m && p.charAt(j+1) == '*')
                    dp[i][j] = dp[i][j+2] || pre && dp[i+1][j];
                else
                    dp[i][j] = pre && dp[i+1][j+1];
            }
        }
        return dp[0][0];
    }

#221 Maximal Square

Sol
dp[i][j] denotes the side length of the maximum square which the right bottom corner is(i,j)
--base case:
dp[0][0] = matrix[i][j]
dp[0][j] = matrix[i][j]
dp[i][0] =matrix[i][j]
--Iterative:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
max_area = max(max_area, dp[i][j] ^2)
--return:
renew the largest square while iterative
max_area

public int maximalSquare(char[][] matrix) {
        int n = matrix.length;
        int m = n == 0 ? 0 : matrix[0].length;
        int[][] dp = new int[n][m];
        int max_area = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(i == 0 || j == 0) dp[i][j] = matrix[i][j] - 48;
                else if(matrix[i][j] == '1'){
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                }
                max_area = Math.max(dp[i][j] * dp[i][j], max_area);
            }
        }
        return max_area;
    }

#322 Coin Change

Sol
dp[i] denotes the minimum number of coins that make up number i
--base case:
dp[0] = 0;
--iterative:
dp[i] = min(dp[i-c]) + 1 for c in coin[];
--return
dp[n-1]

public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);
        dp[0] = 0;
        for(int i = 1; i <= amount; i++){
            for(int coin : coins){
                if(coin <= i){
                    dp[i] = Math.min(dp[i-coin] + 1, dp[i]);
                } 
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

#787 Cheapest Flights Within K Stops

Sol
dp[i][j] denotes the Cheapest Flights from start to j within i stops
--base case:
dp[i][src] = 0
--iterative:
for i in (1...k+1]
for each flight f
dp[i][f[1]] = min(dp[i][f[1]], dp[i-1][f[0]] + f[2])
--return
dp[k+1][dst]

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        double[][] dp = new double[K+2][n];
        for(double[] row:dp) Arrays.fill(row, 1e9);
        dp[0][src] = 0;
        for(int i = 1; i <= K+1; i++){
            dp[i][src] = 0;
            for(int j = 0; j < flights.length; j++){
                dp[i][flights[j][1]] = Math.min(dp[i][flights[j][1]], dp[i-1][flights[j][0]] + flights[j][2]);
            }
            
        }
        return dp[K+1][dst] >= 1e9? -1 : (int)dp[K+1][dst];
    }

double因为Integer会有错误

#1035 Uncrossed Lines

Sol
dp[i][j] denotes the number of Uncrossed Lines between A[0...i-1] and B[0...j-1]
--base case
dp[0][0] = 0
dp[0][j] = 0
dp[i][0] = 0
--iterative:
if(A[i] == B[j]) dp[i][j] = dp[i-1][j-1] + 1
else dp[i][j] = MAX(dp[i-1][j], dp[i][j-1])
--return
dp[n][m]

public int maxUncrossedLines(int[] A, int[] B) {
        int n = A.length, m = B.length;
        int[][] dp = new int[n+1][m+1];
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= m; j++){
                if(i == 0 || j == 0) dp[i][j] = 0;
                else{
                    if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                    else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }

[Three-dimensional]

#87 Scramble String

Sol
dp[i][j][k] denotes whether s2[j...j+k] is the scramble string of s1[i...i+k]. (k is the length)
--base case:
dp[i][j][0] = true
dp[i][j][1] = s1[i] == s2[j]
--Iterative:
for i, j, k
for m in (0...k):
dp[i][j][k] = dp[i][j][m] && dp[i+m][j+m][k-m]
|| dp[i][j+k-m][m] && dp[i+m][j][k-m]
--return:
dp[0][0][len]

public boolean isScramble(String s1, String s2) {
        int len = s1.length();
        boolean[][][] dp = new boolean[len][len][len+1];
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
            }
        }

        for(int k = 2; k <= len; k++){
            for(int i = 0; i <= len-k; i++){
                for(int j = 0; j <= len-k; j++){
                    for(int m = 1; m < k; m++)
                        if(dp[i][j][m] && dp[i+m][j+m][k-m]
||  dp[i][j+k-m][m] && dp[i+m][j][k-m]){
                            dp[i][j][k] = true;
                            break;
                        }
                        
                    
                }
            }
        }
        return dp[0][0][len];
    }

DFS会更快

#980 Unique Paths III

Sol

#741 Cherry Pickup

Sol
dp[r1][c1][c2] denotes the max cherry we can pick up from (r1, c1) to (n, n) and from(r1+c1-c2, c2) to (n, n)
--base case:
dp[n-1][n-1][n-1] = grid[n-1][n-1]
--itertive
dp[r][i][j] = grid[r][i] == 1 ? 1:0 + grid[r+i-j][j] == 1? 1: 0
+MAX(
dp[r][i+1][j+1]
dp[r+1][i][j]
dp[r+1][i][j+1]
dp[r][i+1][j]
)
--return
dp[0][0][0]

    int[][][] dp;
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        dp = new int[n][n][n];
        for (int[][] layer: dp)
            for (int[] row: layer)
                Arrays.fill(row, Integer.MIN_VALUE);
        return Math.max(0, help(grid, 0, 0, 0));
    }
    public int help(int[][] grid, int r1, int c1, int c2){
        int r2 = r1 + c1 - c2;
        int n = grid.length;
        if(r1 == n || r2 == n || c1 == n || c2 == n) return -999999;
        if(grid[r1][c1] == -1 || grid[r2][c2] == -1) return -999999;
        if(r1 == n-1 && c1 == n-1) return grid[r1][c1]; // base case
        if(dp[r1][c1][c2] != Integer.MIN_VALUE) return dp[r1][c1][c2];
        int res = grid[r1][c1] == 1 ? 1 :0;
        if(c1 != c2) res += grid[r2][c2] == 1 ? 1 :0;
        res += Math.max(
            Math.max(help(grid,r1, c1+1, c2+1), help(grid,r1+1, c1, c2+1)), 
            Math.max(help(grid,r1, c1+1, c2), help(grid,r1+1, c1, c2))
        );
        
        dp[r1][c1][c2] = res;
        return res;
    }

[Leetcode][DP]动态规划相关题目汇总/分析/总结

[Unified Dimensional]

#70 Climbing Stairs

#91 Decode Ways

#120 Triangle

#139 Word Break

#140 Word Break II

#198 House Robber

#213 House Robber II

#279 Perfect Squares

#263 Ugly Number

#264 Ugly Number II

[Two-dimensional]

#516 Longest Palindromic Subsequence

#97 Interleaving String

#62 Unique Paths

#63 Unique Paths II

#64 Minimum Path Sum

#72 Edit Distance

#10 Regular Expression Matching

#221 Maximal Square

#322 Coin Change

#787 Cheapest Flights Within K Stops

#1035 Uncrossed Lines

[Three-dimensional]

#87 Scramble String

#980 Unique Paths III

#741 Cherry Pickup

猜你喜欢

热点阅读