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

题目汇总

132. 分割回文串 II困难（看过题解的思路之后可以自己做出来）

139. 单词拆分中等[✔]

140. 单词拆分 II困难（？？？自己是做不出来的）

152. 乘积最大子数组中等[✔]

174. 地下城游戏困难（值得注意，边界 问题需要好好理解）

188. 买卖股票的最佳时机 IV困难（一个通用方法团灭 6 道股票问题）

198. 打家劫舍简单[✔]

213. 打家劫舍 II中等[✔]

221. 最大正方形中等[✔]

132. 分割回文串 II困难

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

思路：动态规划

看的这个题解https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/dong-tai-gui-hua-by-liweiwei1419-2/
dp[i]表示前缀子串 s[0:i] （包括索引 i 处的字符）符合要求的最少分割次数
如果 s[j + 1, i] 是回文串，则 dp[i] 就是在 dp[j] 的基础上多一个分割。

class Solution {//执行用时 :1170 ms, 在所有 Java 提交中击败了20.88%的用户
    public int minCut(String s) {
        int len = s.length();
        if(len < 2)
            return 0;
        int[] dp = new int[len];
        dp[0] = 0;
        for (int i = 0; i < len; i++) {
            dp[i] = i;
        }
        for(int i = 1;i < len;i++){
            if(isPalindrome(s,0,i)){
                dp[i] = 0;
                continue;
            }
            for(int j = 0;j < i;j++){
                 if(isPalindrome(s, j+1, i)){
                     dp[i] = Math.min(dp[i], dp[j] + 1);
                 }
            }
        }
    return dp[len - 1];
    }

    private boolean isPalindrome(String s, int left, int right){
        while(left < right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }  
            left++;
            right--;
        }
        return true;
    }
}

对判断是否为回文子串的方法优化，创建二维数组

class Solution {//执行用时 :15 ms, 在所有 Java 提交中击败了63.34%的用户
    public int minCut(String s) {
        int len = s.length();
        if(len < 2)
            return 0;
        int[] dp = new int[len];
        dp[0] = 0;
        for (int i = 0; i < len; i++) {
            dp[i] = i;
        }
        //创建二维数组用于记录子串s[a:b]是否为回文串
        boolean[][] checkPalindrome = new boolean[len][len]; 
        //根据所给的字符串s，遍历，记录子串s[a:b]是否为回文串
        for (int right = 0; right < len; right++) {
            // 注意：left <= right 取等号表示 1 个字符的时候也需要判断
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left) == s.charAt(right) && (right - left <= 2 || checkPalindrome[left + 1][right - 1])) {
                    checkPalindrome[left][right] = true;
                }
            }
        }

        for(int i=1;i<len;i++){
            if(checkPalindrome[0][i]){
                dp[i] = 0;
            }
            for(int j=0;j<i;j++){
                 if(checkPalindrome[j+1][i]){
                     dp[i] = Math.min(dp[i], dp[j] + 1);
                 }
            }
        }
       
    return dp[len - 1];
    }
   
}

139. 单词拆分中等

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

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

使用 2 个下标指针 i 和 j ，其中 i 是当前字符串从头开始的子字符串的长度， j 是当前子字符串的拆分位置，拆分成 (0,j) 和 (j+1,i)两部分。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {//执行用时 :11 ms, 在所有 Java 提交中击败了43.64%的用户
        int len = s.length();
        boolean[] dp = new boolean[len+1];//dp[i]表示字符串s的前i个字符能否拆分成wordDict
        dp[0] = true;
        for(int i=1;i<=len;i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&wordDict.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
    return dp[len];
    }
}

140. 单词拆分 II困难

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中**增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例：
输入: s = "catsanddog"，wordDict = ["cat", "cats", "and", "sand", "dog"]
输出: [ "cats and dog", "cat sand dog" ]

思路：动态规划

以下代码来自https://leetcode-cn.com/problems/word-break-ii/solution/dong-tai-gui-hua-hui-su-qiu-jie-ju-ti-zhi-python-d/，其中dfs的部分自己写不明白。

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {//执行用时 :11 ms, 在所有 Java 提交中击败了75.07%的用户
        int len = s.length();
        // 状态定义：长度为 i 的子字符串是否符合题意
        boolean[] dp = new boolean[len + 1];

        // 预处理
        Set<String> wordSet = new HashSet<>();
        for (String word : wordDict) {
            wordSet.add(word);
        }

        // 这个状态的设置非常关键，说明前部分的字符串已经在 wordSet 中
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                // dp[l] 写在前面会更快一点，否则还要去切片，然后再放入 hash 表判重
                if (dp[j] && wordSet.contains(s.substring(j, i))  ) {
                    dp[i] = true;
                    // 这个 break 很重要，一旦得到 dp[r] = True ，循环不必再继续
                    break;
                }
            }
        }
        List<String> res = new ArrayList<>();
        if (dp[len]) {
            LinkedList<String> queue = new LinkedList<>();
            dfs(s, len, wordSet, res, queue, dp);
            return res;
        }

        return res;
    }

    private void dfs(String s, int end, Set<String> wordSet, List<String> res, LinkedList<String> queue, boolean[] dp) {
        if (end == 0) {
            StringBuilder stringBuilder = new StringBuilder();
            for (String word : queue) {
                stringBuilder.append(word);
                stringBuilder.append(" ");
            }
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            res.add(stringBuilder.toString());
            return;
        }

        for (int i = 0; i < end; i++) {
            if (dp[i]) {
                String suffix = s.substring(i, end);
                if (wordSet.contains(suffix)) {
                    queue.addFirst(suffix);
                    dfs(s, i, wordSet, res, queue, dp);
                    queue.removeFirst();
                }
            }
        }
    }
}

152. 乘积最大子数组中等

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

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

遍历数组时计算当前最大值，不断更新
令max为当前最大值，则当前最大值为 max = max(max * nums[i], nums[i])
由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值min，min = min(min * nums[i], nums[i])
当负数出现时则max与min进行交换再进行下一步计算

//2020.06.09
class Solution {//执行用时 :2 ms, 在所有 Java 提交中击败了90.26%的用户
    public int maxProduct(int[] nums) {
        if(nums == null || nums.length < 1)
            return 0;
        int max = 1;
        int min = 1;
        int res = Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            //出现负数，交换最大值最小值
            if(nums[i] < 0){
                int temp = max;
                max = min;
                min = temp;
            }
            max = Math.max(nums[i], max * nums[i]);
            min = Math.min(nums[i], min * nums[i]);
            res = Math.max(res, max);
        }
    return res;
    }
}

174. 地下城游戏困难

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
| -2 (K) | -3 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
说明:
骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
相似题目：62. 不同路径中等、63. 不同路径 II中等、64. 最小路径和中等

思路：动态规划

开始从左上角到右下角动态规划，但是因为不知道后面的格子，就无法确定初始生命值。所以从右下角到左上角动态规划， dp[i][j]表示从 (i, j) 这个格子走到右下角所需要的最低初始健康点数，最小值是 1 。
调了好久，边界问题容易出错。
https://leetcode-cn.com/problems/dungeon-game/solution/dong-tai-gui-hua-ji-qi-shu-xue-tui-dao-by-mzh1996/解释的很好

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {//执行用时 :2 ms, 在所有 Java 提交中击败了96.62%的用户
        int rows = dungeon.length;
        int cols = dungeon[0].length;
        int[][] dp = new int[rows][cols];
        //初始化右下角的值
        dp[rows-1][cols-1] = Math.max(1, 1-dungeon[rows-1][cols-1]);
        //初始化最后一列
        for(int i=rows-2;i>=0;i--){
            dp[i][cols-1] = Math.max(1, dp[i+1][cols-1]-dungeon[i][cols-1]);
        }
        //初始化最后一行
        for(int j=cols-2;j>=0;j--){
            dp[rows-1][j] = Math.max(1, dp[rows-1][j+1]-dungeon[rows-1][j]);
        }
        for(int i=rows-2;i>=0;i--){
            for(int j=cols-2;j>=0;j--){
                dp[i][j] = Math.max(1, Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]);
            }
        }
    return dp[0][0];
    }
}

188. 买卖股票的最佳时机 IV困难

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
相关题目：
121. 买卖股票的最佳时机简单
122. 买卖股票的最佳时机 II简单
123. 买卖股票的最佳时机 III困难
309. 最佳买卖股票时机含冷冻期中等
714. 买卖股票的最佳时机含手续费中等

思路：动态规划

labuladongd大佬的一个通用方法团灭 6 道股票问题https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-w-5/
很受用，感谢大佬的题解分析

class Solution {//执行用时 :11 ms, 在所有 Java 提交中击败了39.91%的用户
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if (k > len / 2) 
            return maxProfit_k_inf(prices);

        int[][][] dp = new int[len][k + 1][2];
        for (int i = 0; i < len; i++) 
            for (int j = k; j >= 1; j--) {
                if (i - 1 == -1) { 
                    dp[0][j][0] = 0;
                    dp[0][j][1] = -prices[0];
                    continue;
                }
                dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);     
            }
        return dp[len - 1][k][0];
    }
    //k为正无穷
    int maxProfit_k_inf(int[] prices) {
        int len = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
        }
        return dp_i_0;
    }

}

198. 打家劫舍简单

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

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

由于不能进入在相邻的房屋偷窃，所以在第 i 间房屋可盗窃的最大值，就是取在第 i-1 间房屋可盗窃的最大值，和在第 i-2 间房屋可盗窃的最大值加上当前房屋的值二者的最大值。

//2020.06.09
class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
    public int rob(int[] nums) {
        if(nums == null || nums.length < 1)
            return 0;
        int[] dp = new int[nums.length + 1];//从前i个房屋中能够偷窃到的最高金额
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i=2;i<=nums.length;i++){
            //nums[0]对应是第1个房间，所以第i个房间是nums[i-1]
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
        }
    return dp[nums.length];
    }
}

213. 打家劫舍 II中等

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

思路：动态规划

相比上一题，区别在于这道题中第一个房屋和最后一个房屋是紧挨着的，也就是第一个房子和最后一个房子中只能选择一个偷窃，因此可以转化为两个子问题：
不偷窃第一个房子时，即为(1, len)中求最大值
不偷窃最后一个房子时，即为(0, len-1)中求最大值
以上两种情况的较大值为最终结果。

class Solution {
    public int rob(int[] nums) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
        if(nums.length == 0)
            return 0;
        if(nums.length == 1)
            return nums[0];
        int[] dp1 = new int[nums.length];//从前i个房屋中能够偷窃到的最高金额
        int[] dp2 = new int[nums.length];//从前i个房屋中能够偷窃到的最高金额
        dp1[0] = 0;
        dp1[1] = nums[0];
        dp2[0] = 0;
        dp2[1] = nums[1];
        //(0,len-1)不偷窃最后一个房子时
        for(int i=2;i<nums.length;i++){
            dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i-1]);
        }
        //(1, len)不偷窃第一个房子时
        for(int i=2;i<nums.length;i++){
            dp2[i] = Math.max(dp2[i-1],dp2[i-2]+nums[i]);
        }
    return Math.max(dp1[nums.length-1],dp2[nums.length-1]);
    }
}

221. 最大正方形中等

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

思路：动态规划

写出动态转移方程是关键。若某格子值为 1 ，则以此为右下角的正方形的、最大边长为：上面的正方形、左面的正方形或左上的正方形中，最小的那个，再加上此格。
感谢题解https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/

class Solution {
    public int maximalSquare(char[][] matrix) {//执行用时 :7 ms, 在所有 Java 提交中击败了46.38%的用户
        if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0)
            return 0;
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row+1][col+1];//dp[i + 1][j + 1] 表示 以第 i 行、第 j 列为右下角的正方形的最大边长
        int l = 0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(matrix[i][j] == '1'){
                    dp[i+1][j+1] = Math.min(Math.min(dp[i+1][j],dp[i][j+1]),dp[i][j])+1;
                    l = Math.max(l,dp[i+1][j+1]);
                }       
            }
        }
    return l*l;
    }
}