1.动态规划（一）

2020-06-08 本文已影响0人今天柚稚了么

https://leetcode-cn.com/tag/dynamic-programming/

题目汇总

5. 最长回文子串中等

10. 正则表达式匹配困难（能看懂题解，是自己考虑不周）

32. 最长有效括号困难（？）

44. 通配符匹配困难[✔]

53. 最大子序和简单[✔]

62. 不同路径中等[✔]

63. 不同路径 II中等[✔]

64. 最小路径和中等[✔]

70. 爬楼梯简单[✔]

72. 编辑距离困难（？？？）

动态规划常常适用于有重叠子问题和最优子结构性质的问题，往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
几乎所有的动态规划解决方案，首先会创建一个一维或多维数组 DP 来保存中间子解的值，以及通常数组最后一个值代表最终解，动态转移方程是关键，从上一个状态到下一个状态之间可能存在一些变化，以及基于这些变化的最终决策结果。我们把这样的表达式称为状态转移方程。
第 1 步：定义状态，dp[i] 表示.....
第 2 步：考虑状态转移方程，dp[i] = .....
第 3 步：考虑初始化
第 4 步：考虑输出
第 5 步：考虑状态压缩

5. 最长回文子串中等

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"

思路：动态规划，时间复杂度为O(n²)

如果一个字符串的头尾两个字符都不相等，那么这个字符串一定不是回文串；
如果一个字符串的头尾两个字符相等
（1）如果里面的子串是回文，整体就是回文串；
（2）如果里面的子串不是回文串，整体就不是回文串。

class Solution {
    public String longestPalindrome(String s) {//执行用时 :137 ms, 在所有 Java 提交中击败了33.81%的用户
        int len = s.length();
        if(len < 2)
            return s;//此时一定是回文串
        boolean[][] dp = new boolean[len][len];//定义状态dp[i][j]表示子串s[i, j]是否为回文子串
        for(int i=0;i<len;i++){
            dp[i][i] = true;//初始化，单个字符一定是回文串
        }
        int maxLen = 1;
        int start = 0;
        for(int i=len-2;i>=0;i--){//i要降序（因为dp[i][j] = dp[i+1][j-1]）
            for(int j=i+1;j<len;j++){//j要升序（因为dp[i][j] = dp[i+1][j-1]）
                if(s.charAt(i) == s.charAt(j)){
                    if(j-i<3){//(j-1)-(i+1)+1<2，即为[i+1, j-1]不构成区间，边界条件，dp值可以直接判断
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];//状态转移方程
                    }
                }else{
                    dp[i][j] = false;
                }
                if(dp[i][j]){//子串s[i, j]是回文子串时，记录长度和起始位置
                    int currentLen = j-i+1;
                    if(currentLen > maxLen){
                        maxLen = currentLen;
                        start = i;
                    }
                }
            }
        }   
    return s.substring(start, start+maxLen);//最长的回文子串
    }
}

参考大佬回答，还有中心扩散法和Manacher 算法的详解。

10. 正则表达式匹配困难

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。'.' 匹配任意单个字符，'*'匹配零个或多个前面的那一个元素。
所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入:
字符串s = "aa"
字符串规律p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
字符串s = "aa"
字符串规律p = "a*"
输出: true
解释: 因为 *代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

思路：动态规划

看了好久的题解才看明白，分好几种情况讨论，初始化是关键。

class Solution {//执行用时 :3 ms, 在所有 Java 提交中击败了90.91%的用户
    public boolean isMatch(String s, String p) {
        //dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        //初始化
        for(int j=1;j<p.length()+1;j++){
            if(j == 1) //比如p = b， 只有一个元素，这时候一定是false
                dp[0][j] = false;
            if(p.charAt(j-1) == '*' && dp[0][j-2])//比如p = b*，这时看dp[0][j-2]是否为true
                dp[0][j] = true;
        }

        for(int i=1;i<=s.length();i++){
            for(int j=1;j<=p.length();j++){
                //最简单的情况，字符相等或者p的字符是‘.'
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.')
                    dp[i][j] = dp[i-1][j-1];
                    
                else if(p.charAt(j-1) == '*'){
                    //如果p的*前边的字符和s当前字符相等或者p的字符是‘.'
                    //三种可能
                    //匹配0个，比如aa aaa*  dp[i][j]=dp[i][j-2]
                    //匹配1个，比如aab aab*  dp[i][j]=dp[i][j-1]
                    //匹配多个，比如aabb aab*  就看aab 和aab*是否能匹配上，即dp[i][j]=dp[i-1][j]
                    if(p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2)=='.'){
                        dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2];
                    }
                    //如果p的*前边的字符和s当前字符不相等或者p的字符不是‘.'
                    //那就把*和*前边一个字符都不要了
                    else{
                        dp[i][j] = dp[i][j-2];
                    }
                }else{
                    dp[i][j] = false;
                }
            }
        }
    return dp[s.length()][p.length()];
    }
}

32. 最长有效括号困难

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

思路：动态规划，时间复杂度为O(n)

class Solution {
    public int longestValidParentheses(String s) {//执行用时 :2 ms, 在所有 Java 提交中击败了88.57%的用户
        int len = s.length();
        int[] dp = new int[len+1];//dp[i]表示以下标i的字符结尾的最长有效子串的长度
        Arrays.fill(dp, 0);
        int maxVal = 0;
        for(int i=1;i<len;i++){
           if (s.charAt(i) == ')') {
                if (s.charAt(i-1) == '(') {
                    dp[i] = 2;
                    if (i - 2 >= 0) {
                        dp[i] = dp[i] + dp[i - 2];
                    }
                } else if (dp[i - 1] > 0) {
                    if ((i - dp[i - 1] - 1) >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if ((i - dp[i - 1] - 2) >= 0) {
                            dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                        }
                    }
                }
            }
              
        maxVal = Math.max(maxVal, dp[i]);
        }
    return maxVal;
    }
}

44. 通配符匹配困难

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。'?' 可以匹配任何单个字符。'*'可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:
输入:s = "aa"，p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

思路：动态规划

与 10. 正则表达式匹配非常相似，做完正则表达式匹配题，这道题可以自己独立完成，感觉自己没那么菜了，终于可以了。

class Solution {//执行用时 :36 ms, 在所有 Java 提交中击败了48.23%的用户
    public boolean isMatch(String s, String p) {
        int slen = s.length();
        int plen = p.length();
        //dp[i][j] : 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配
        boolean[][] dp = new boolean[slen+1][plen+1];
        //初始化
        dp[0][0] = true;
        for(int j=1;j<=plen;j++){
            if(p.charAt(j-1) == '*' && dp[0][j-1])
                dp[0][j] = true;//s 为空，与 p 匹配
        }

        for(int i=1;i<=slen;i++){
            for(int j=1;j<=plen;j++){
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?')
                    dp[i][j] = dp[i-1][j-1];
                else if(p.charAt(j-1) == '*')  
                    //dp[i][j - 1] 表示 * 代表的是空字符，例如 ab, ab*
                    //dp[i - 1][j] 表示 * 代表的是非空字符，例如 abcd, ab*
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
        }
    return dp[slen][plen];
    }
}

53. 最大子序和简单

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

思路一：动态规划，时间复杂度为O(n)

class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了95.08%的用户
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length < 1)
            return 0;
        //dp[i]定义为以num[i]结尾的最大连续子数组和
        int[] dp = new int[nums.length];
        dp[0] = nums[0];//初始值
        for(int i=1;i<nums.length;i++){
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);//状态转移方程
        }
        //结果是 dp[0]...dp[i] 中最大值，遍历一遍dp[i]求最大值
        int res = dp[0];
        for (int i = 1; i < nums.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

思路二：贪心算法，时间复杂度为O(n)

思路三：分冶法，时间复杂度为O(nlogn)

62. 不同路径中等

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？

输入: m = 7, n = 3，输出: 28

思路：动态规划

dp[i][j]的值是从起始点走到(i, j)的路径数。由于机器人每次只能向下或者向右移动一步，dp[i][j]的值就是第 i 行第 j 列这个格子的上面格子的值加上左边格子的值，也就是dp[i][j] = dp[i-1][j] + dp[i][j-1]，其中第一行 dp[0][j]=0，第一列 dp[i][0]=0

class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
    public int uniquePaths(int m, int n) {
        if(m < 0 || n < 0)
            return 0;
        if(m == 0 || n == 0)
            return 1;
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){ 
                if (i == 0 || j == 0) {     //最上一行或者最左一列
                    dp[i][j] = 1;
                }
                else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];//状态转移方程
                }        
            }
        }
    return dp[m-1][n-1];
    }
}

63. 不同路径 II中等

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径

向右 -> 向右 -> 向下 -> 向下

向下 -> 向下 -> 向右 -> 向右

思路：动态规划

与62. 不同路径相比只是增加了障碍物，大致思路一样的。

class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了62.86%的用户
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid[0].length == 0) {
            return 0;
        }
        int row = obstacleGrid.length;//行数
        int col = obstacleGrid[0].length;//列数
        int[][] dp = new int[row][col];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(obstacleGrid[i][j]==1){
                    dp[i][j] = 0;
                }else{
                    if(i==0 && j==0) dp[i][j]=1;
                    else if(i==0) dp[i][j]=dp[i][j-1];//第一行
                    else if(j==0) dp[i][j]=dp[i-1][j];//第一列
                    else dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
            
        }
    return dp[row-1][col-1];
    }
}

64. 最小路径和中等

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

思路：动态规划

分为四种情况
(1)当i = 0, j = 0时，其实就是起点
(2)当j=0时，grid[i][j] = grid[i-1][j] + grid[i][j]
(3)当i=0时，grid[i][j] = grid[i][j-1]+ grid[i][j]
(4)当i，j均不为0时，grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1])+ grid[i][j]

class Solution {//执行用时 :3 ms, 在所有 Java 提交中击败了89.88%的用户
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(i==0&&j==0)
                    continue;
                else if(i==0){
                    grid[i][j] += grid[i][j-1];
                }
                else if(j==0){
                    grid[i][j] +=  grid[i-1][j];
                }  
                else{
                    grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
                }
            }
        }
       
        return grid[row-1][col-1];
    }
}

70. 爬楼梯简单

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意:给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

思路：动态规划，时间复杂度为O(n)

用f(n)表示到达第n阶台阶的方法数目，初始化f(1)=1,f(2)=2，表示到达第1阶台阶共有1种方法，到达第2阶台阶共有两种方法。由于每次只能登1个或2个台阶，那么登第三个台阶时，最后一步一定是从第二个台阶（3-1）跨一步，或者从第一个台阶(3-2)跨两步，这二者之一，那么到达第三个台阶的方法数目其实就是到达第二个台阶的方法数目加上到达第一个台阶的方法数目，即f(3)=f(1)+f(2)。后面的以此类推。
第 i 阶可以由以下两种方法得到：
在第 (i-1)阶后向上爬 1 阶。
在第 (i-2) 阶后向上爬 2 阶。
所以到达第 i 阶的方法总数就是到第 (i-1) 阶和第 (i-2) 阶的方法数之和。

class Solution {
    public int climbStairs(int n) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
        if(n==1){
            return 1;
        }
        int dp[]=new int[n+1];//dp[i]=j为需要i阶，有j种方法可以爬到楼顶
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];//状态转移方程
        }
    return dp[n];
    }
}

72. 编辑距离困难

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符、删除一个字符、替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

1.动态规划（一）

题目汇总

5. 最长回文子串中等

10. 正则表达式匹配困难（能看懂题解，是自己考虑不周）

32. 最长有效括号困难（？）

44. 通配符匹配困难[✔]

53. 最大子序和简单[✔]

62. 不同路径中等[✔]

63. 不同路径 II中等[✔]

64. 最小路径和中等[✔]

70. 爬楼梯简单[✔]

72. 编辑距离困难（？？？）

5. 最长回文子串中等

思路：动态规划，时间复杂度为O(n²)

10. 正则表达式匹配困难

思路：动态规划

32. 最长有效括号困难

思路：动态规划，时间复杂度为O(n)

44. 通配符匹配困难

思路：动态规划

53. 最大子序和简单

思路一：动态规划，时间复杂度为O(n)

思路二：贪心算法，时间复杂度为O(n)

思路三：分冶法，时间复杂度为O(nlogn)

62. 不同路径中等

思路：动态规划

63. 不同路径 II中等

思路：动态规划

64. 最小路径和中等

思路：动态规划

70. 爬楼梯简单

思路：动态规划，时间复杂度为O(n)

72. 编辑距离困难

猜你喜欢

热点阅读

1.动态规划（一）

题目汇总

5. 最长回文子串中等

10. 正则表达式匹配困难（能看懂题解，是自己考虑不周）

32. 最长有效括号困难（？）

44. 通配符匹配困难[✔]

53. 最大子序和简单[✔]

62. 不同路径中等[✔]

63. 不同路径 II中等[✔]

64. 最小路径和中等[✔]

70. 爬楼梯简单[✔]

72. 编辑距离困难（？？？）

5. 最长回文子串中等

思路：动态规划，时间复杂度为O(n2)

10. 正则表达式匹配困难

思路：动态规划

32. 最长有效括号困难

思路：动态规划，时间复杂度为O(n)

44. 通配符匹配困难

思路：动态规划

53. 最大子序和简单

思路一：动态规划，时间复杂度为O(n)

思路二：贪心算法，时间复杂度为O(n)

思路三：分冶法，时间复杂度为O(nlogn)

62. 不同路径中等

思路：动态规划

63. 不同路径 II中等

思路：动态规划

64. 最小路径和中等

思路：动态规划

70. 爬楼梯简单

思路：动态规划，时间复杂度为O(n)

72. 编辑距离困难

猜你喜欢

热点阅读

思路：动态规划，时间复杂度为O(n²)