动态规划-力扣题解

“一题二写，三数之和，题解四瞅五瞄六瞧，水平还七上八下九流，十分辣鸡。”

“十推九敲，八种思路，用光七情六欲五感，在这里四覆三翻二挠，一拳爆屏。”

[1] 定义部分参考了力扣官方力扣小卡片-动态规划

[2] 使用方法和力扣题目来自于开源模板-动态规划

[3] 文章结构和代码全凭个人理解、错误之处敬请指出；除标注外皆原创、保留权力

1 如何使用动态规划

​ 动态规划（Dynamic programming，简称 DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划不是某一种具体的算法，而是一种算法思想：若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。[1]

​ 现阶段的刷题就是为了面试撕代码，所以第一节直接讲怎么用，第二节再讲DP是什么。

1.1 使用场景[2]

• 满足以下条件之一
  • 求最大/最小值（Maximum/Minimum ）
  • 求是否可行（Yes/No ）
  • 求可行个数（Count(*) ）
• 满足不能排序或者交换（Can not sort / swap ）

1.2 四点要素[2]

• 状态 State
  • 灵感，创造力，存储小规模问题的结果
• 方程 Function
  • 状态之间的联系，怎么通过小的状态，来算大的状态
• 初始化 Intialization
  • 最极限的小状态是什么, 起点
• 答案 Answer
  • 最大的那个状态是什么，终点

1.3 示例模板-斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

​ 以最为简单的斐波拉契数作为例子，方便理解动态规划算法的使用流程。四点要素中我觉得最重要的是状态，状态用来存储小规模问题的结果、状态的选择需要创造力，但就应试考试而言、我们通过经验来弥补就好了。其次是状态转移方程、基本只要能列出方程就离解题不远了。本题而言、方程已经直接给了就可以直接上手：

• 动态规划 dp[i]表示F(i)的值
• 初始化 dp[0]=0, dp[1]=1; 终点求dp[n]
• 状态转移方程 dp[i]=dp[i-1]+dp[i-2];

模板代码：

class Solution {
    public int fib(int n) {
        if(n==0) return 0; //特殊情况先判断
        int[] dp = new int[n+1];
        //初始化
        dp[0]=0; dp[1]=1;
        //迭代过程
        for(int i=2;i<=n;++i){
            dp[i] = dp[i-1]+dp[i-2];
        }
        //终点
        return dp[n];
    }
}

​ 至于怎么减少空间复杂度，重复利用dp数组的空间，其实是细支末节，并不很难，代码如下：

class Solution {
    public int fib(int n) {
        if(n<2) return n; //特殊情况先判断
        int[] dp = new int[3]; //重复利用空间
        //初始化
        dp[0]=0; dp[1]=1;
        //迭代
        for(int i=2;i<=n;++i){
            dp[2] = dp[0]+dp[1];
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        //终点
        return dp[2];
    }
}

2 介绍动态规划[1]

​ 应用这种动态规划算法思想解决问题的可行性，对子问题与原问题的关系，以及子问题之间的关系这两方面有一些要求，它们分别对应了最优子结构和重复子问题。

最优子结构

一个问题的最优解是由它的各个子问题的最优解决定的。将子问题的解进行组合可以得到原问题的解是动态规划可行性的关键。在解题中一般用状态转移方程描述这种组合。找到了最优子结构，也就能推导出一个状态转移方程 $f(n)$

重复子问题

重复子问题规定的是子问题与子问题的关系。动态规划可以保证每个重叠的子问题只会被求解一次。当重复的问题很多的时候，动态规划可以减少很多重复的计算。

动态规划算法中关于最优子结构和重复子问题的理解的关键点：

• 证明问题的方案中包含一种选择，选择之后留下一个或多个子问题
• 设计子问题的递归描述方式
• 证明对原问题的最优解包括了对所有子问题的最优解
• 证明子问题是重叠的（这一步不是动态规划正确性必需的，但是如果子问题无重叠，则效率与一般递归是相同的）

3 力扣题解

120. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标i或 i + 1 。

思路：

• 这题状态的选择很有创造性，从底部往上动态查找
• dp[i][j]表示 第i行的j节点出发 到第n行的最小路径和
• 初始化 dp为原集合 目标dp[0][0]
• 动态迭代 dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1])+arr[i][j]

代码：空间优化就是一维数组，代码就不再列出了

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int n = triangle.get(m-1).size();
        if(m<=1) return triangle.get(0).get(0);
        int[][] dp = new int[m][n];
        //初始化最后一层
        for(int j=0;j<n;j++){
            dp[m-1][j] = triangle.get(m-1).get(j);
        }
        //动态迭代
        for(int i=m-2;i>=0;i--){
            for(int j=0;j<triangle.get(i).size();j++){
                dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

思路：

• 原地动态规划 dp[i][j]表示从左上角到i,j处的最小路径和
• 初始化dp[0][i], dp[j][0]累计即可 终点dp[m-1][n-1]
• 动态规划方程 dp[i][j] = grid[i][j]+ Math.min(dp[i-1][j],dp[i][j-1])

代码：

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

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2

思路：

• 状态就是某网格的路径数 有障碍物时当前为0
• dp[i][j]表示从左上角到i,j位置的路径数目
• 初始化 第一行第一列为1 如果出现障碍物后面全0 终点dp[m-1][n-1]
• 动态迭代 有障碍物则0，如果没有就dp[i][j]=dp[i-1][j]+dp[i][j-1]

代码：其实如果新建一个dp[][]数组后细节处更不易出错

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if(obstacleGrid[0][0]==1) return 0;//排除干扰
        //初始化 第一列和第一行
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0]==1){
                for(int j=i;j<m;j++) obstacleGrid[j][0]=0;
                break;
            }else {
                obstacleGrid[i][0]=1;
            }
        }
        //注意这里第一行要从第二个开始了 因为第一列初始化已经修改了值！！
        for(int i=1;i<n;i++){
            if(obstacleGrid[0][i]==1){
                System.out.println(i);
                for(int j=i;j<n;j++) obstacleGrid[0][j]=0;
                break;   
            }else {
                obstacleGrid[0][i]=1;
            }
        }
        //动态迭代
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]==1){
                    obstacleGrid[i][j]=0;
                }else{
                    obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
                }
            }
        }
        return obstacleGrid[m-1][n-1];
    }
}

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

思路：动态规划——维护每个点是否可达的数组

• dp[i] 表示能否跳到i+1这个节点
• dp[0] = true 求dp[n-1];
• 动态迭代求dp[i]时，从i-1处向前找

代码：

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if(nums[0]==0&&n>1) return false;
        boolean[] dp = new boolean[n]; //默认为false
        dp[0] = true;
        for(int i=1;i<n;i++){
            //动态迭代求dp[i]时，从i-1处向前找
            for(int j=i-1;j>=0;j--){
                if(dp[j]==true&&i-j<=nums[j]){
                    dp[i]=true;
                    break;
                }
            }
            if(dp[i]==false) return false;
        }
        return dp[n-1];
    }
}

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

这个动态规划怎么这么慢？

class Solution {
    public String longestPalindrome(String s) {
        //动态规划 dp[i][j]表示从索引i到j的子串是否是回文串
        //动态迭代 dp[i][j] = dp[i+1][j-1] && s.charAt(i)==s.charAt(j);
        //两层循环 外层长度从1到n  内层索引 i从0到n-l
        //初始化 需要初始长度为1 和长度为2 的dp
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int maxLength = 1;
        int left = 0, right =0;
        for(int length=1;length<=n;length++){
            for(int i = 0;i<=n-length;i++){
                int j = i+length-1;  //[i,j]
                if(length==1) dp[i][j] = true;
                else if(length==2) dp[i][j] = s.charAt(i)==s.charAt(j);
                else
                    dp[i][j] = dp[i+1][j-1] && s.charAt(i)==s.charAt(j);

                if(dp[i][j]&&length>maxLength){
                    maxLength = length;
                    left = i;
                    right = j;
                }

            }
        }
        return s.substring(left,right+1);
    }
}

这题的频率不是一般的高，暴力解法也来爽一爽

class Solution {
    public String longestPalindrome(String s) {
        //想先写一个暴力解法
        int maxLength = 1;
        int left=0, right=1;
        for(int i=0;i<s.length();i++){
            for(int j=i+1;j<=s.length();j++){
                String cur = s.substring(i,j);
                if(isPalindrome(cur)&& cur.length()>maxLength){
                    left = i; right = j;
                    maxLength = right - left;
                }
            }

        }
        return s.substring(left,right);
    }
    //判断一个字符串是否是回文串
    private boolean isPalindrome(String s){
        if(s.length()==1) return true;
        for(int i=0;i<s.length()/2;i++){
            if(s.charAt(i)!=s.charAt(s.length()-i-1))
            return false;
        }
        return true;
    }
}

132. 分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成 [“aa”,”b”] 这样两个回文子串。

思路：

• dp[i]表示1到i的子串的最小分割次数 dp = new int[n+1]; dp[]的长度比字符串s大1
• dp[i]的初始化为dp[i-1]+1,,并且dp[1]=0; dp[0]=-1，终点dp[n]
• dp[i]的求解需要利用遍历，j从0遍历到i-1 如果有[j+1,i]部分是回文的(对应于s(j,i-1) )则dp[i]=Math.min(dp[i],dp[j]+1)

代码：运行相当之慢，好像判断是否回文哪里可以用动态规划优化一下（回头再看吧…)

class Solution {
    public int minCut(String s) {
        int n = s.length();
        if(n<=1) return 0;
        int[] dp = new int[n+1];
        dp[0]=-1; dp[1]=0;

        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+1;
            for(int j=0;j<i;j++){
                //[j+1,i]为回文则取小值
                if(isBack(s,j,i-1)){
                    dp[i] = Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[n];
    }

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

300. 最长递增子序列

• 和分割回文子串的最小次数是一类题，dp[i]的求解需要 dp[]数组从0往i的遍历 找找迭代方程中的需要的那个元素
• dp[i]表示以i索引元素结尾的严格增子序列的长度！！！dp[i]非递增，而是代表类它自己那个递增序列的长度
• 初始化 dp[0]=1; dp[i]=1 终点不是dp[n-1]，而是**dp[i]数组的最大值**
• 动态迭代 j有0到i-1,if(nums[j]<nums[i]) 则dp[i] =max(dp[i], dp[j]+1),,,
• 用一个maxResult记录dp[]数组的最大值

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 1;
        int maxResult=1;
        for(int i=1;i<n;++i){
            dp[i]=1;
            for(int j=0;j<i;++j){
                if(nums[i]>nums[j]) dp[i]=Math.max(dp[i],dp[j]+1);
            }
            maxResult=Math.max(dp[i],maxResult);
        }
        return maxResult;
    }
}

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

​ 思路：连续三道找状态dp[i]，需要遍历dp[]数组i之前的所有元素、来判断dp[i]的取值了！！ 都是复杂度为O(n2)的DP

• dp[i]表示字符串第i-i个元素，是否可以被拆分为字典中出现的词
• dp[0]表示无字符串为true， 终点dp[n]
• 动态迭代 当dp[j]=true&&[j+1,i]位于字典中，对应s的索引为s[j,i-1]
• 用set集合判断是否在字段中

​ 代码：

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true; //因为求dp[1]要用到dp[0]索引定义dp长度为n+1！！！
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(dp[j]==true && wordDictSet.contains(s.substring(j,i)) ){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

思路：想复杂了没想到是一个简单的DP

• 当text[i]==text[j]时 dp[i][j] = dp[i-1][j-1]+1
• 否则 dp[i][j] = max(dp[i-1][j],dp[i][j-1])
• 初始化dp[0][0] = 0第一行第一列都为0 终点dp[m][n]
• 定义m+1 n+1维的数组就很完美

代码：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(); int n = text2.length();
        int[][]dp = new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(text1.charAt(i-1)==text2.charAt(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[m][n];
    }
}

72. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

思路：

• dp[i][j]表示word1前i个转换成word2前j个 所需使用的最小操作数
• 初始化 第一行dp[0][j]=j 第一列dp[i][0]=i //终点dp[m][n]
• 动态规划,若word1.charAt(i-1)==word2.charAt(j-1) 则dp[i][j]=dp[i-1][j-1]表示不需要操作
• 若不相等 则dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
• 定义m+1 n+1维的数组就很完美
  • 因为要用到i-1 j-1,所以需要从1开始循环，dp[0][0]表示都为空时的状态，dp[1][1]代表第一个元素的状态，所以dp[m][n]是终点

代码：

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];
        //初始化第一行第一列为i,j
        dp[0][0] =0;
        for(int i=1;i<=m;i++) dp[i][0] = i;
        for(int j=1;j<=n;j++) dp[0][j] = j;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = Math.min( Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1; //分别对应：增加、增加、替换
            }
        }
        return dp[m][n];
    }
}

4 面试高频题

221. 最大正方形

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

思路：这题的关键是状态的确定 还有迭代方程

• dp[i][j]表示以[i][j]为右下角，且只包含 1 的正方形的边长最大值
• 初始化：第一行第一列最大为1，并且就等于matrix矩阵的值
• 需要用一个maxLength记录最大边长
• 迭代方程 dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;

代码：

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int maxLength=0;
        int[][] dp = new int[m][n];
        //初始化
        for(int i=0;i<m;i++){
            if(matrix[i][0]=='1') {
                dp[i][0] = 1;
                maxLength=1;
            }
        }
        for(int j=0;j<n;j++){
            if(matrix[0][j]=='1'){
                dp[0][j] = 1;
                maxLength=1;
            }
        }
        //动态迭代
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[i][j]=='1')
                dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
                if(dp[i][j]>maxLength) maxLength=dp[i][j];
            }
        }
        return maxLength*maxLength;
    }
}

44. 通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

思路：动态规划，有变化的地方在于p，需要分类考虑

• 状态dp[i][j]表示s的前i个字符和p的前j个字符是否匹配成功
• 初始化 dp[0][0]=true, dp[i][0]=false; dp[0][j]仅p前j个全为*才为真； 终点dp[m][n]
• 动态迭代 如果p[j]为小写字母，dp[i][j] = s[i]==p[j] && dp[i-1][j-1]
• 如果 p[j]为？, dp[i][j] = dp[i-1][j-1]
• 如果 p[j]为*， dp[i][j] = dp[i][j-1] || dp[i-1][j]; 分别表示 *使用和不使用的情况 (这里难想一点)

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean [m+1][n+1];
        //初始化
        dp[0][0] =true;
        for(int j=1;j<=n;j++){
            if(p.charAt(j-1)=='*'){
                dp[0][j]=true;
            }else{
                break;
            }
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(p.charAt(j-1)=='?'){
                    dp[i][j] = dp[i-1][j-1];
                }else if(p.charAt(j-1)=='*'){
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }else{//为小写字母
                    dp[i][j] = s.charAt(i-1)==p.charAt(j-1) && dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}

32. 最长有效括号

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

思路：

• 动态规划 状态dp[i]表示索引i的字符结尾的最长有效子串的长度
• 初始化dp[i]=0, 终点：求dp[]数组的最大值
• 动态迭代 当s[i]为'(' 时dp[i]=0;
• 1形如"...()" 当s[i]=')'&&s[i-1]='(' 时 dp[i]=dp[i-2]+2;
• 2形如"...))" 当s[i]=')'&&s[i-1]=')' 时 当前一个子串之前的有(能与s[i]的)配对时，需 +2+(之前的子串长度
  • if(s[i-dp[i-1]-2]=='(') 则dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]
• 注意每一次赋值判断之前都要判断s和dp是否可能发生越界！！细节太多了！

代码：

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

什么时候需要定义dp[]数组长度+1，还真实一个苦恼的问题

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

思路：

• 状态：dp[i][0] 第i天不持有的最大利润;dp[i][1] 第i天持有的最大利润
• 初始化:dp[0][0] = 0; dp[0][1] = -prices[0] ；终点：dp[n-1][0]
• 只能买卖一次 说明买入的时候 资产为-prices[i]

代码：

class Solution {
    public int maxProfit(int[] prices) {
        //只能买卖一次 说明买入的时候 资产为-price[i]
        int n = prices.length;
        int[][] dp = new int[n][2];
        //初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i=1;i<n;i++){
            dp[i][0] = Math.max(dp[i-1][1]+prices[i],dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
        }
        return dp[n-1][0];
    }
}

减少空见复杂度,重复利用dp[]数组的空间

• % 2还可以写成 & 1，这里为了保证可读性，选用 % 2

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int [][] dp = new int[2][2];
        if (n<1) return 0;
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1;i<n;i++){
            dp[i%2][0] = Math.max(dp[(i-1)%2][0],dp[(i-1)%2][1]+prices[i]);
            dp[i%2][1] = Math.max(dp[(i-1)%2][1],-prices[i]);
        }
        return dp[(n-1)&1][0]; //与运算博大精深啊
        //return Math.max(dp[1][0],dp[0][0]);
    }
}

123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

思路:

• 状态 dp[i][j]表示索引i天状态j下的最大利润 j=0表示未买入 1表示买入一个 2表示卖出一个 3表示买入第二个 4表示卖出第二个
• 初始化 第一天：dp[0][0]=dp[0][2]=dp[0][4]=0; dp[0][1]=dp[0][3]=-prices[0] 终点dp[n-1][2or4]
• 动态迭代 dp[i][0] = 0; dp[i][1] =max(-prices[i],dp[i-1][1]); dp[i][2] = max(dp[i-1][1]+prices[i],dp[i-1][2]);
• dp[i][3]=max(dp[i-1][2]-prices[i],dp[i-1][3]); dp[i][4]=max(dp[i-1][3]+prices[i],dp[i-1][4]);

代码：

class Solution {
    public int maxProfit(int[] prices) {
        //状态 dp[i][j]表示索引i天状态j下的最大利润 j=0表示未买入 1表示买入一个 2表示卖出一个 3表示买入第二个 4表示卖出第二个
        int n = prices.length;
        int[][] dp = new int[n][5];
        //初始化
        dp[0][0]=0; dp[0][1]= dp[0][3] =-prices[0];
        dp[0][2]= dp[0][4]=0;
        for(int i=1;i<n;i++){
            dp[i][1] = Math.max(-prices[i],dp[i-1][1]);
            dp[i][2] = Math.max(dp[i-1][1]+prices[i],dp[i-1][2]);
            dp[i][3] = Math.max(dp[i-1][2]-prices[i],dp[i-1][3]);
            dp[i][4] = Math.max(dp[i-1][3]+prices[i],dp[i-1][4]);
        }
        return Math.max(dp[n-1][2],dp[n-1][4]);
    }
}

代码二：空间优化

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] dp = new int[5];
        //状态：0表示未交易 1表示买入一次 2表示卖出一次 3表示买入两次 4表示卖出两次
        //初始化
        dp[0] = 0;
        dp[1] = -prices[0];
        dp[2] = 0;
        dp[3] = -prices[0];
        dp[4] = 0;
        for (int i = 0; i < n; i++) {
            dp[0] = 0;
            dp[1] = Math.max(dp[1], dp[0] - prices[i]);
            dp[2] = Math.max(dp[2], dp[1] + prices[i]);
            dp[3] = Math.max(dp[3], dp[2] - prices[i]);
            dp[4] = Math.max(dp[4], dp[3] + prices[i]);
        }
        return Math.max(dp[2],dp[4]);
    }
}

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

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

思路：

• 状态（0到2k） 0表示未交易 1表示买入一次 2表示卖出一次…2k-1表示买入k次，2k表示卖出k次
• 初始化：dp[0]始终为0；dp[1]= - prices[0]；dp[2-end]初始化为一个小值
• 动态迭代：
  • 外层循环为考虑的天数，从i=1:n-1
  • 内层循环为遍历所有状态：从j=1:2k
  • 如果当前状态索引j为奇数，也就是手头有股票的情况dp[j] = max(dp[j], dp[j - 1] - prices[i])
  • 如果当前状态索引j为偶数，也就是手头没有股票的情况dp[j] = max(dp[j], dp[j - 1] + prices[i])
• 终点为数组dp[] 的最大值

代码：

class Solution {
    public int maxProfit(int k, int[] prices) {
        //dp[]:2k+1;  dp[2*k-1]买入k次  dp[2*k]表示卖出k次
        int n = prices.length;
        k = Math.min(k,n/2); //最多进行n/2次交易！！
        if(n<=0||k<=0) return 0;
        int[] dp = new int[2*k+1];
        //初始化dp为小值
        dp[1] = -prices[0];
        for(int i=2;i<=2*k;i++) dp[i]= Integer.MIN_VALUE;
        //按天数动态迭代
        for(int i=1;i<n;i++){
            for(int j=1;j<=2*k;j++){
                if(j%2==0) dp[j] = Math.max(dp[j-1]+prices[i],dp[j]);
                if(j%2==1) dp[j] = Math.max(dp[j-1]-prices[i],dp[j]);
            }
        }
        //找最大值
        int res = 0;
        for(int i=2;i<=2*k;i=i+2){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

718. 最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3, 2, 1] 。

思路：

• //dp[i][j] 表示n1以i开头、n2以j开头的子数组的最长公共子数组长度 即nums1[i:end] nums2[j:end]
• //初始化dp[m-1][n-1]=0or1; dp[m-1][j]=0or1; dp[i][n-1]=0or1; 终点dp[0][0]，求数组dp[][]的最大值
• //动态迭代 nums1[i]==nums2[j]? dp[i][j] = dp[i+1][j+1]+1:0;

代码

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        //一个反序推导的题
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m][n];
        int res = 0;
        //初始化
        for(int j=0;j<n;j++){
            if(nums1[m-1]==nums2[j]) dp[m-1][j]=1;
        }
        for(int i=0;i<m;i++){
            if(nums1[i]==nums2[n-1]) dp[i][n-1]=1;
        }

        for(int i=m-2;i>=0;i--){
            for(int j=n-2;j>=0;j--){
                dp[i][j] =  nums1[i]==nums2[j]? dp[i+1][j+1]+1:0;  
                if(dp[i][j]>res) res = dp[i][j];          
            }
        }
        return res;
    }
}

也可以直接定义dp[][]数组的长度为[m+1,n+1],那样就不用初始化了

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 ：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路：

• dp[i]表示偷窃前i个房屋所能获得的最大金额
• 初始化 dp[0]=nums[0] dp[1]=Max(dp[0],nums[1]); 终点dp[n-1]
• 动态迭代 dp[i] = Max(dp[i-1],dp[i-1]+nums[i]);

代码: 如果使用滚动数组可以减少空间复杂度、不列出了

class Solution {
    public int rob(int[] nums) {
        //dp[i]表示偷窃前i个房屋所能获得的最大金额
        int n = nums.length;
        if(n==1) return nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0]; dp[1]=Math.max(dp[0],nums[1]);
        for(int i=2;i<n;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
}

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

思路：

• dp[i] 表示前i件范围盗窃 最大金额
• dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
• 如果第一件盗窃 则盗窃范围为[0,n-2]
• 如果第一间不盗窃 范围为[1,n-1]
• 因为要用到dp[i-2]，所以用dp[0]=0表示不盗窃！！

代码一：两个dp[]数组

class Solution {
    public int rob(int[] nums) {
        //相当于两个动态规划的叠加 1盗窃第一间房[0,n-2] 2不盗窃第一间房[1,n-1]
        
        int n = nums.length;
        if(n==1) return nums[0];
        int[] dp1 = new int[n];
        int[] dp2 = new int[n];
        dp1[1] = nums[0]; //盗窃第一间房
        dp2[1] = nums[1]; //盗窃了第二间房
        for(int i=2;i<n;i++){
            dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i-1]);
            dp2[i] = Math.max(dp2[i-1],dp2[i-2]+nums[i]);
        }
        return Math.max(dp1[n-1],dp2[n-1]);
    }
}

代码二：滚动数组优化空间

class Solution {
    public int rob(int[] nums) {
        //如果第一件盗窃 则盗窃范围为[0,n-2]
        //如果第一间不盗窃 范围为[1,n-1]
        int[] dp = new int[6]; //前3 后3
        int n = nums.length;
        if(n==1) return nums[0];
        if(n==2) return Math.max(nums[0],nums[1]);
        if(n==3) return Math.max(nums[2],Math.max(nums[0],nums[1]));
        //初始化 至少有四个元素
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1],nums[0]);
        dp[3] = nums[1];
        dp[4] = Math.max(nums[2],nums[1]);
        //两种情况循环次数是一样的 注意i的大小就好了
        for(int i=2;i<=n-2;++i){
            //第一种情况
            dp[2] = Math.max(dp[1],dp[0]+nums[i]);
            dp[0] = dp[1];
            dp[1] = dp[2];
            //第二种情况
            dp[5] = Math.max(dp[4],dp[3]+nums[i+1]);
            dp[3] = dp[4];
            dp[4] = dp[5];
            //System.out.println(dp[5]);
        }
        return Math.max(dp[2],dp[5]);
    }
}

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

思路：注意负负得正

• 因为 负负得正，一个负数乘一个很小的负数可能得到一个很大的乘积，所以对每个i索引要分别保存最大乘积和最小乘积
• dp[i][0]表示i索引元素结尾的连续子数组的最大乘积 dp[i][1]表示最小乘积
• 初始化dp[0][0]=dp[0][1]=nums[0]; 终点dp[i][0]数组的最大值
• 动态迭代 dp[i][0] = max(dp[i-1][0]*numd[i],dp[i-1][1]*nums[i],nums[i]); dp[i][1] = min(...)

代码：

class Solution {
    public int maxProduct(int[] nums) {
        //dp[i][0]表示i索引元素结尾的连续子数组的最大乘积 dp[i][1]表示最小乘积
        int n = nums.length;
        int[][] dp = new int[n][2];
        int max = dp[0][0] = dp[0][1]=nums[0];
        for(int i=1;i<n;i++){
            dp[i][0] = Math.max(Math.max(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i]),nums[i]);
            dp[i][1] = Math.min(Math.min(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i]),nums[i]);
            max = Math.max(max,dp[i][0]);
        }
        return max;
    }
}

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，”11106” 可以映射为：

“AAJF” ，将消息分组为 (1 1 10 6)
“KJF” ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

思路：

• 动态规划 迭代方程需要分一下类：单个字符结尾/两个字符结尾
• dp[i]表示第i个字符前的子串解码方法的总数，因为要用到i-2所以令dp[0]=1代表空字符串
• 初始化 dp[0]=dp[1]=1; 终点dp[n]
• 动态迭代 单个字符结尾s[i]!='0' dp[i] += dp[i-1];
• 两个字符结尾 s[i-1]!='0'&& s[i-1]s[i]<=26 dp[i] += dp[i-2];

代码：

class Solution {
    public int numDecodings(String s) {
        //动态规划 迭代方程需要分一下类：单个字符结尾/两个字符结尾
        //dp[i]表示第i个字符前的子串解码方法的总数
        //因为要用到i-2所以令dp[0]=1代表空字符串
        if(s.charAt(0)=='0') return 0;
        int n = s.length();
        int[] dp = new int[n+1];
        dp[0] = dp[1] =1;
        for(int i=2;i<=n;i++){
            if(s.charAt(i-1)!='0') dp[i] +=dp[i-1];
            if(s.charAt(i-2)!='0' && (s.charAt(i-2)-'0')*10+(s.charAt(i-1)-'0')<=26 )
                dp[i] += dp[i-2];
        }
        return dp[n];
    }
}

887. 鸡蛋掉落

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

示例 1：
输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 
如果它没碎，那么肯定能得出 f = 2 。 
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。 

示例 2：
输入：k = 2, n = 6
输出：3

示例 3：
输入：k = 3, n = 14
输出：4

思路：动态规划+二分查找

• 动态规划 dp[i][j]表示用i个鸡蛋确定j层楼房的f值 的最小操作数
• 初始化 dp[i][1]= 1 一层楼房 抛一次就确定了 ；dp[1][j]=j 一个鸡蛋确定j层楼房 从下往上试直到摔破共j次
• 终点 dp[k][n]
• 动态迭代 外层i从2到k个鸡蛋 内层j从2层到n层楼房； 如果不用二分、第三层 x从1到n
• dp[k][n] = 1+ min( max( dp[k-1,x-1] , dp[k,n-x]) ) 摔破/没摔破 取所有x的小值
• dp[k-1][x-1]随x递增 dp[k][x-k]随x递减,，注意画这两个单调数列的图（两条直线），就明白如何用二分了，取两个函数的大值，就是上边的折线，然后找整个折线的最小值
• 使用二分找到 dp[k-1][x-1] < dp[k][n-x] 的最后一个x0，，然后比较获得min(T1(x0+1), T2(x0))

代码：

class Solution {
    public int superEggDrop(int k, int n) {
        //动态规划 dp[i][j]表示用i个鸡蛋确定j层楼房的f值 的最小操作数
        int[][] dp = new int[k+1][n+1];
        for(int i=1;i<=k;i++) dp[i][1]= 1;
        for(int j=1;j<=n;j++) dp[1][j]= j;

        for(int i=2;i<=k;i++){
            for(int j=2;j<=n;j++){
                //如果不用二分算法
                // int min = n+1;
                // for(int x=1;x<=j;x++){
                //     dp[i][j] = 1 + Math.min(min, Math.max(dp[i-1][x-1],dp[i][j-x])) 
                // }

                //二分算法
                int left = 1, right = j;
                //要找T1小于T2的最大x0
                int x0=0;
                while(left+1<right){
                    x0 = left+(right-left)/2; 
                    if( dp[i-1][x0-1]<dp[i][j-x0]){
                        left = x0;
                    }else if(dp[i-1][x0-1]>dp[i][j-x0]){
                        right = x0;
                    }else{
                        right = x0;
                    }
                }
                //判断right和left谁才是真正要找的x0的位置
                if(dp[i-1][right-1]<=dp[i][j-right]) x0=right;
                else x0= left;

                //所以最小值 min(T1(x0+1),T2(x0))
                dp[i][j] =1 + Math.min(dp[i-1][x0+1-1], dp[i][j-x0]);
            }
        }
        return dp[k][n];
    }
}

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

思路：

• 动态规划 dp[i][j]表示索引i之前的数能够构造出结果j的表达式数目
• 因为属于j[-1000,1000], 所以事实上用dp[i][j+1000]，
• 动态规划 dp[i][j+1000-nums[i]] += dp[i-1][j+1000]; //对应-号
• dp[i][j+1000+nums[i]] += dp[i-1][j+1000]; //对应+号
• i外层循环[0，n-1]； j内层循环[-1000，1000]
• 不知道初始化谁，就手动循环一遍发现只用i=0, dp[0][j+1000]+=1就好了,其中j=nums[0]/-nums[0],一定要+=防止出现多个0的情况！！、其他必然为0
• 终点 dp[n-1][target+1000];
• 对于j的遍历来说，是在等式的右边体现的，这里与其他动规相比较特别，就是用[j]更新[j+/-nums[i]]
  • 如果dp[i - 1][j]==0就没有进入更新的必要

代码:

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //动态规划 dp[i][j]表示索引i之前的数能够构造出结果j的表达式数目
        // 因为属于j[-1000,1000],所以事实上用dp[i][j+1000]，
        int n = nums.length;
        int[][] dp = new int[n][2001];
        //初始化
        dp[0][nums[0]+1000] += 1;
        dp[0][-nums[0]+1000] += 1;
        for(int i=1;i<n;i++){
            for(int j=-1000;j<=1000;j++){
                //对于j的遍历来说，是在等式的右边体现的，这里与其他动规相比较特别
                //就是用[j]更新[j+/-nums[i]]
                if (dp[i - 1][j + 1000] > 0){ //如果==0就没有进入更新的必要
                    dp[i][j+1000-nums[i]] += dp[i-1][j+1000]; //对应-号
                    dp[i][j+1000+nums[i]] += dp[i-1][j+1000]; //对应+号
                }
            }
        }
        return dp[n-1][target+1000];
    }
}

97. 交错字符串

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
提示：a + b 意味着字符串 a 和 b 连接。

思路:

• 开始我想错了 以为i、j之差不能超过1,没必要没必要
• dp[i][j]表示s1的前i个与s2的前j个能否交错组成s3的前(i+j)个s3，，s1+s2与s3长度若不相等直接返回false
• 初始化dp[0][j]=true仅当s2[0:j-1]=s3[0:j]; dp[i][0]=true仅当s1[0:i-1]=s3[0:i]
• 动态迭代 dp[i][j] = dp[i-1][j]&&s1[i-1]==s3[i+j-1] || dp[i][j-1]&&s2[j-1]==s3[i+j-1]

代码：

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        //dp[i][j]表示s1的前i个与s2的前j个能否交错组成s3的前(i+j)个s3
        int m =s1.length(), n = s2.length();
        if(n+m!=s3.length()) return false;
        boolean[][] dp=new boolean[m+1][n+1];
        //初始化
        dp[0][0] = true;
        for(int i=1;i<=m;i++){
            if(s1.charAt(i-1)==s3.charAt(i-1)){
                dp[i][0] = true;
            }else{
                break;
            }
        }
        for(int i=1;i<=n;i++){
            if(s2.charAt(i-1)==s3.charAt(i-1)){
                dp[0][i] = true;
            }else{
                break;
            }
        }

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j] = ( dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i-1+j) ) || 
                        (dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1));
            }
        }
        return dp[m][n];

    }
}

5 背包问题(领扣）

我为什么这么菜？还是直接以题代学。领扣上面有全套的背包题。

125 · 背包问题（二）

描述

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?

A[i], V[i], n, m 均为整数你不能将物品进行切分你所挑选的要装入背包的物品的总大小不能超过 m每个物品只能取一次

输入：

m = 10
A = [2, 3, 5, 7]
V = [1, 5, 2, 4]

输出：

9

解释：

装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9

就是最基础的01背包问题，每一个物品只能用一次。

思路1：二维数组

• dp[i][j]表示前i个物品装入j大小的背包 的最大总价值数
• 初始化dp=[i][0]0; 终点dp[n][m]
• 动态迭代：i的范围[1,n] j的范围[0,m] 状态分别对应将第i个物品装入背包和不装入背包两种情况

$$
dp[i][j]=max(dp[i-1][j], dp[i-1][j-A[i-1]]+V[i-1])
$$

代码1：

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int[] V) {
        //dp[i][j]表示前i个物品装入j大小的背包 的最大总价值数
        int n = A.length;
        int[][] dp = new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                if(j-A[i-1]<0) dp[i][j]=dp[i-1][j];
                else dp[i][j] = Math.max( dp[i-1][j], dp[i-1][j-A[i-1]]+ V[i-1] );
            }
        }
        return dp[n][m];
    }
}

思路2：空间优化的一维数组

我们发现，欲求 dp[i][j]需要使用dp[i-1][j]和dp[i-1][j-A[i-1]]两种状态，显然就是计算i时需要i-1时候的状态！！ 令状态dp[j]标识默认i个物品时容量为j能装的最大价值数，每遍历完一次、就更新了该数组一次。状态转移方程：
$$
dp[j] = Math.max(dp[j], dp[j-A[i-1]]+ V[i-1] )
$$
但是这时出现了一个问题：如果j仍然从0遍历到最大容量m，，，dp[j-A[i-1]]总是先于dp[j]更新，所以更新过程，用到了更新的数组的值、当然就有问题了。。

这个时候就需要反向遍历,j仍然从m遍历到0，，计算索引靠右边的dp[j]时，利用的是上一个数组中的dp[j]和没有更新的索引位置较小的dp[j-x]

动态规划的要素如下：

• dp[j]标识默认i个物品时容量为j的背包能装的最大价值数
• 初始化dp[j]=0标识0个物品时的最大价值 , 终点dp[m]标识n个物品时容量m背包的最大价值数
• 动态迭代 j从m迭代到0，状态转移方程如上 ，i还是从1迭代到n，，时间并没有优化！！

代码2：

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int[] V) {
        int[] dp = new int[m+1];
        int n = A.length;
        for(int i=1;i<=n;i++){
            for(int j=m; j>=0;j--){
                if(j-A[i-1]>=0) dp[j] = Math.max(dp[j],dp[j-A[i-1]]+V[i-1]);
            }
        }
        return dp[m];
    }
}

92 · 背包问题

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]

输入：

数组 = [3,4,8,5]
backpack size = 10

输出：

9

思路：就是01背包问题，然后体积和价值是同一个数组

代码：一维数组

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        //其实就是01背包问题，然后体积和价值是同一个数组
        int[] dp = new int[m+1];
        int n = A.length;
        for(int i=1;i<=n;i++){
            for(int j=m;j>=A[i-1];j--){
                dp[j] = Math.max(dp[j], dp[j-A[i-1]]+A[i-1]);
            }
        }
        return dp[m];
    }
}

440 · 背包问题 III

给定 n 种物品, 每种物品都有无限个. 第 i 个物品的体积为 A[i], 价值为 V[i].

再给定一个容量为 m 的背包. 问可以装入背包的最大价值是多少?

不能将一个物品分成小块.放入背包的物品的总大小不能超过 m.

样例 1:

输入: A = [2, 3, 5, 7], V = [1, 5, 2, 4], m = 10
输出: 15
解释: 装入三个物品 1 (A[1] = 3, V[1] = 5), 总价值 15.

就是最经典的完全背包问题，每一个物品只能无限次。

思路1：三层循环

• dp[i][j]表示前i个物品任意取，背包容量为j时的最大价值
• 初始化 dp[i][0]=0; 终点dp[n][m]
• 动态迭代 第i个物品最多使用的个数是 m/A[i-1] k取0到m/A[i-1]
• dp[i][j] = max( dp[i-1][j-k*A[i-1]]+k*V[i-1])

代码1：就嗯循环

public class Solution {
    /**
     * @param A: an integer array
     * @param V: an integer array
     * @param m: An integer
     * @return: an array
     */
    public int backPackIII(int[] A, int[] V, int m) {
        //dp[i][j]表示前i个物品任意取，背包容量为j时的最大价值
        int n = A.length;
        int[][] dp = new int[n+1][m+1];
        for(int i= 1;i<=n;i++){
            for(int j=0;j<=m;j++){
                //dp[i][j] = dp[i-1][j];
                for(int k =0;k<=m/A[i-1];k++){
                    if(j-k*A[i-1]>=0)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*A[i-1]]+k*V[i-1] );
                }
            }
        }
        return dp[n][m];
    }
}

思路2：O(nm)的算法，翻转01背包的遍历顺序即可！！这里摘用一下《背包九讲》中的解释

首先想想为什么 01 背包中要按照 j 递减的次序来循环。让 j 递减是为了保证第i次循环中的状态 dp[i, j] 是由状态 dp[i − 1, j − Ai] 递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第 i 件物品”这件策略时，依据的是一个绝无已经选入第 i 件物品的子结果 dp[i − 1, j − Ai]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果 dp[i, j − Ai]，所以就可以并且必须采用 j递增的顺序循环。这就是这个简单的程序为何成立的道理。

• //完全背包 时间空间都优化

• //dp[j]表示示前i个物品任意取，背包容量为j时的最大价值

• //初始化 dp[0]=0; 终点dp[m]

• //动态迭代 j从0迭代到m，，i还是从1迭代到n，，O(mn)时间复杂度！！
  $$
  dp[j] = Math.max(dp[j], dp[j-A[i-1]]+ V[i-1] )
  $$

代码：

public class Solution {
    /**
     * @param A: an integer array
     * @param V: an integer array
     * @param m: An integer
     * @return: an array
     */
    public int backPackIII(int[] A, int[] V, int m) {
        //完全背包 时间空间都优化
        //dp[j]表示示前i个物品任意取，背包容量为j时的最大价值
        int n = A.length;
        int[] dp = new int[m+1];
        for(int i=1;i<=n;i++){
            for(int j=A[i-1];j<=m;j++){
                dp[j] = Math.max(dp[j], dp[j-A[i-1]]+V[i-1]);
            }
        }
        return dp[m];
    }
}