算法学习-动态规划，纸老虎打倒他（持续更新中）_括号生成 动态规划

动态规划（DP）是面试考察的重点和难点，为了能够顺利通过大厂面试中的手撕代码环节，笔者记录了自己对于这个知识点的刷题汇总，希望可以理清思路加深理解，亲身实践，帮大家拿下动态规划。

基础知识

主要参考了宫水三叶大神以及卡尔哥的刷题分类，根据各种专题进行针对性训练，对刷题中的感悟和难点进行整理。同时笔者之前手敲了一遍Carl大神的动态规划专题，但是里面主要是按照题型来分的，相对来说知识体系没有那么全面，不过动归也算是入了门。

动态规划关键步骤如下：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序

前两步是最难想的，在刷题的过程中要注意前两步的体会。一些些感悟如下：

1. dp数组状态是搜寻答案过程中的中间步骤，可以根据答案要我们求什么来定义中间状态
2. 当发现题目具有状态间关系的时候就可以考虑DP，比如路径只有规定的方向到达、整数拆分最大值后面可以利用、二叉树形态的个数可以利用。考虑后面状态与前面状态的关系，考虑后面的状态怎么由前面推导出来，具有一定的逆向思维。
3. DP数组不一定非得从下标为0初始化，也不一定需要定义和输入参数一样的长度，递推公式也不一定要从第一个元素开始，需要根据状态转移方程往好理解好算灵活定义。

线性DP

相关题目

45.跳跃游戏II

吐槽一下自己，明明五个月前AC了，现在又不会了，还是没有掌握思想。
才发现当时自己是贪心模拟做的，这里想到的是定义每个dp状态为该位置的最小移动次数。

//O(N^2),超时边缘了
class Solution {
    public int jump(int[] nums) {
        int len=nums.length;
        int[]dp=new int[len];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                if(j+nums[j]>=i) dp[i]=Math.min(dp[i],dp[j]+1);
            }
        }
        return dp[len-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

70.爬楼梯

class Solution {
    public int climbStairs(int n) {
        if(n<=2) return n;
        int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

746.使用最小花费爬楼梯

$dp[i]$表示爬上第i（从1开始）个台阶（还没有从第i个台阶抬脚，因此到达终点的意思是就是dp[n]），需要花费的体力。需要爬到整个数组以上，即dp[len]。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len=cost.length;
        int[]dp=new int[len+1];
        dp[0]=0; //第一步不花体力
        dp[1]=0;
        for(int i=2;i<=len;i++){
            dp[i]=Math.min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
        }
        return dp[len];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

62.不同路径

这题看起来一眼DFS ，尝试使用如下代码，直接超出时间限制，相当于是遍历二叉树，时间复杂度为O(2^(m+n-1))。当测试用例是19 13的时候就超过了

class Solution {
    public int uniquePaths(int m, int n) {
        return dfs(1,1,m,n);
    }
    int dfs(int i,int j,int m,int n){
        if(i>m||j>n) return 0;
        if(i==m&&j==n) return 1;
        return dfs(i+1,j,m,n)+dfs(i,j+1,m,n);
    }
}
1
2
3
4
5
6
7
8
9
10

遂改用二维线性DP，咱也不知道为什么要改，但根据题解理解起来，好像某一状态的路径总数只与两个方向有关。这里dp数组的初始化是难点。 最上边和最左边的路径数只能为1.

//O(M*N)
class Solution {
    public int uniquePaths(int m, int n) {
        //代表走到一个位置的方案数
        int[][]dp=new int[m][n];
        for(int i=0;i<m;i++) dp[i][0]=1;
        for(int i=0;i<n;i++) dp[0][i]=1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

63.不同路径2

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        int[][]dp=new int[m][n];
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0]==1) break;
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++){
            if(obstacleGrid[0][i]==1) break;
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                //对于障碍始终为0，不进行状态更新
                if(obstacleGrid[i][j]==1) continue;
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

343.整数拆分

拆分整数最后算出最大乘积背后隐藏的动态规划是，当前数i拆分的最大乘积，和其被拆出一个数j以后，剩余那部分i-j的能够算出的最大乘积有关。

设dp[i]表示整数i可以拆分出来的最大乘积，看到n从2开始，优雅的做法是初始化dp[2]=1，然后循环计算，为了不让内部有dp[1]，因此j只循环到i-2。循环中dp[i]=Math.max(dp[i],...)的逻辑，是将当前dp[i]的最大乘积记录下来，内部Math.max(dp[i-j]*j,(i-j)*j)中(i-j)*j是为了不忽略有些数字拆分成两个数，反倒是它的最大乘积的情况，比如3，拆分成1和2最大乘积为2，如果算1和dp[2]却为1；比如6，拆分成3和3最大乘积为9，如果算3和dp[3]却为6.

class Solution {
    public int integerBreak(int n) {
        int[]dp=new int[n+1];
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<i-1;j++){
                dp[i]=Math.max(dp[i],Math.max(dp[i-j]*j,(i-j)*j));
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

96.不同的二叉搜索树

这题返回的二叉搜索树的种树，即形态种类，而不是搜索树上的节点值是否相同。看到树是一点联想不到DP，能用DP是因为可以利用算出来的节点较少的时候的二叉树的种类。

class Solution {
    public int numTrees(int n) {
        int[]dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=0;j<=i-1;j++){
                dp[i]+=dp[j]*dp[i-1-j];
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

91.解码方法

参考题解解码方法，需要考虑到的是当前字母解码的方式，与前面字母的解码方式有关，同时当前字母是否为0，也决定了是否需要与前面的状态联合。前后的方案数有关系。

1. 当前位置不为0，可以单独解码，也可以在下标大于等于2的时候尝试联合解码，联合解码需要联合数在10到26中。dp[i]和dp[i-1]、dp[i-2]有关
2. 当前位置为0，只能在长度大于等于2的时候，在10和26这个范围里联合解码，dp[i]可能会加上dp[i-2]。

class Solution {
    public int numDecodings(String s) {
        int len=s.length();
        //dp[i]表示有i个数字的时候能组成的方案数
        int[]dp=new int[len+1];
        //没有意义，但是能保证递推方程在dp[2]或者dp[1]的时候正确
        dp[0]=1;
        for(int i=1;i<=len;i++){
            //dp[i]初始化为0
            if(s.charAt(i-1)!='0') dp[i]+=dp[i-1];
            if(i>=2){
                int num= 10*(s.charAt(i-2)-'0')+s.charAt(i-1)-'0';
                if(num>=10&&num<=26) dp[i]+=dp[i-2];
            }
        }
        return dp[len];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

119.杨辉三角2

class Solution {
    public List<Integer> getRow(int rowIndex) {
        int[][]map=new int[rowIndex+1][rowIndex+1];
        for(int i=0;i<=rowIndex;i++){
            for(int j=0;j<=i;j++){
                if(j==0||j==i) map[i][j]=1;
                else map[i][j]=map[i-1][j]+map[i-1][j-1];
            }
        }
        ArrayList<Integer> res=new ArrayList<>();
        for(int i=0;i<=rowIndex;i++){
            res.add(map[rowIndex][i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

338.比特位计数

参考题解奇偶分类 ，理解动态规划和二进制位运算之间的关系。

class Solution {
    public int[] countBits(int n) {
        int[]res=new int[n+1];
        for(int i=1;i<=n;i++){
            if(i%2==1) res[i]=res[i-1]+1;
            else res[i]=res[i/2];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10

688.骑士在棋盘上的概率

考虑后面状态是前面八个方向概率的和，从k步往前推导，遍历顺序为从第0步开始从前往后计算，枚举8个方向。参考宫水三叶的题解.

dp[i][j][p]表示从位置[i,j]出发，使用步数不超过p步，仍然留在棋盘上的概率，其为“八联通”落点概率之和。

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        double [][][]dp=new double[n][n][k+1];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) dp[i][j][0]=1.0;
        }
        int[][]dir={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
        for(int m=1;m<=k;m++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    for(int[]d:dir){
                        int x=i+d[0];
                        int y=j+d[1];
                        if(x<0||x>=n||y<0||y>=n) continue;
                        dp[i][j][m]+=dp[x][y][m-1]/8;
                    }
                }
            }
        }
        return dp[row][column][k];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

22.括号生成

在求N个括号的排列组合时，把第N种情况（也就是N个括号排列组合）视为单独拿一个括号E出来，剩下的N-1个括号分为两部分，P个括号和Q个括号，P+Q=N-1，然后这两部分分别处于括号E内和括号E的右边，各自进行括号的排列组合。

输出所有结果的问题不是只能用回溯，还可以用动态规划，参考题解动态规划

class Solution {
    public List<String> generateParenthesis(int n) {
        //dp[i]代表n=i时，有效的括号组合
        LinkedList<LinkedList<String>> dp=new LinkedList<>();
        LinkedList<String> list0=new LinkedList<>();
        list0.add("");
        LinkedList<String> list1=new LinkedList<>();
        list1.add("()");
        dp.add(list0);
        dp.add(list1);

        //按顺序递推
        for(int i=2;i<=n;i++){
            LinkedList<String> temp=new LinkedList<>();
            for(int j=0;j<=i-1;j++){
                LinkedList<String> listp=dp.get(j);
                LinkedList<String> listq=dp.get(i-1-j);
                for(int p=0;p<listp.size();p++){
                    for(int q=0;q<listq.size();q++){
                        temp.add("("+listp.get(p)+")"+listq.get(q));
                    }
                }
            }
            dp.add(temp);
        }
        return dp.get(n);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

467.环绕字符串中唯一的子字符串

参考负雪明烛大神的图解
子串问题，一般想到「滑动窗口」和「动态规划」。

子串相关的动态规划，一般状态的定义都是「以位置 i 作为结尾的、符合要求的子串长度」。对于本题，我们把状态定义为「p 中，以位置i作为结尾的、在s中存在的最长子串长度」。相同字母结尾的要取dp[i]的最大值。

class Solution {
    public int findSubstringInWraproundString(String p) {
        char[] parray=p.toCharArray();
        int len=parray.length;
        int[] character=new int[26];
        int [] dp=new int[len+1];
        dp[1]=1;
        character[parray[0]-'a']=1;
        for(int i=2;i<=len;i++){
            //处理形如za的情况要取余
            if(parray[i-1]-'a'==(parray[i-2]-'a'+1)%26){
                dp[i]=dp[i-1]+1;
            }else{
                dp[i]=1;
            }
            //以相同字母结尾的取最大
            character[parray[i-1]-'a']=Math.max(character[parray[i-1]-'a'],dp[i]);
        }

        //将所有26个字母结尾的非空子串相加
        int res=0;
        for(int i=0;i<26;i++){
            res+=character[i];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

978.最长湍流子数组

这题参考题解@负雪明烛大神，其中设置一个增长数组一个下降数组的方法值得学习。

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int len=arr.length;
        int[]up=new int[len];
        int[]down=new int[len];
        Arrays.fill(up,1);
        Arrays.fill(down,1);
        int res=1;
        for(int i=1;i<len;i++){
            if(arr[i]>arr[i-1]){
                up[i]=down[i-1]+1;
            }else if(arr[i]<arr[i-1]){
                down[i]=up[i-1]+1;
            }
            res=Math.max(res,Math.max(up[i],down[i]));
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        N=len(arr)
        up=[1]*N
        down=[1]*N
        res=1
        for i in range(1,N):
            if(arr[i]>arr[i-1]):
                up[i]=down[i-1]+1
            elif(arr[i]<arr[i-1]):
                down[i]=up[i-1]+1
            res=max(res,max(up[i],down[i]))
        
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1137.第N个泰波那契数

class Solution {
    public int tribonacci(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 1;
        int[]dp=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

剑指Offer10-I.斐波那契数列

class Solution {
    public int fib(int n) {
        int mod=1000000007;
        if(n<=1) return n;
        long[]dp=new long[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++){
        	//dp数组中的每一个都需要取余
            dp[i]=(dp[i-1]+dp[i-2])%mod;
        }
        return (int)dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

53.最大子数组和

考虑当前位置的子数组和只有两种情况转变而来，前面的最大子数组和加上当前元素，或者就是当前元素重新开始。

class Solution {
    public int maxSubArray(int[] nums) {
        int len=nums.length;
        int ans=Integer.MIN_VALUE;
        int[]dp=new int[len+1];
        dp[0]=0;
        for(int i=1;i<=len;i++){
            dp[i]=Math.max(dp[i-1]+nums[i-1],nums[i-1]);
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

790.多米诺和托米诺平铺

解法1，参考蓝桥杯原题，一维状态，通过动态规划公式推导，算出递推公式。当$i\ge 4$时，$p[i]=dp[i-1]+dp[i-2]+2\ast (dp[i-3]+dp[i-4]+....dp[1])$，i从1开始，$dp[i]$表示从第1列到第$i$列总共有的平铺方式。

class Solution:
    def numTilings(self, n: int) -> int:
        if n==1:
            return 1
        if n==2:
            return 2
        if n==3:
            return 5
        dp=[0]*(n+1)
        dp[1]=1
        dp[2]=2
        dp[3]=5
        i=4
        mod=(10**9)+7
        while i<=n:
            dp[i]=(2*dp[i-1]+dp[i-3])%mod
            i+=1
        return dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解法2，二维状态，严格定义不同状态，通过状态的转换方程进行求解。参考题解，定义四种覆盖状态$dp[i][0]、dp[i][1]、dp[i][2]、dp[i][3]$，分别表示覆盖到第i列的时候有的覆盖方式，定义空状态是为了从前一层更好地铺开L或者一字形状。

class Solution:
    def numTilings(self, n: int) -> int:
        dp=[[0]*4 for _ in range(n+1)]
        dp[0][3]=1
        mod=10**9+7
        for i in range(1,n+1):
            dp[i][0]=dp[i-1][3]%mod
            dp[i][1]=(dp[i-1][2]+dp[i-1][0])%mod
            dp[i][2]=(dp[i-1][0]+dp[i-1][1])%mod
            dp[i][3]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3])%mod
        return dp[n][3]
1
2
3
4
5
6
7
8
9
10
11

799.香槟塔

状态定义，$dp[i][j],i>=1,j>=1$代表第$i$行第$j$列流入的香槟体积，可以大于$1$，代表已装满；递推方程$dp[i][j]$的体积可以由$dp[i-1][j]$和$dp[i-1][j-1]$推导出来，具体为它们多于1的部分各有一半流入进来，即$dp[i][j]=[Math.max(dp[i-1][j]-1,0)+Math.max(dp[i-1][j-1]-1,0)]/2$。

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double [][]dp=new double[101][101];
        // 注意题目中的查询下标都是从0开始的
        dp[1][1]=poured;
        for(int i=2;i<=query_row+1;i++){
            for(int j=1;j<=query_glass+1;j++){
                dp[i][j]=(Math.max(dp[i-1][j]-1,0)+Math.max(dp[i-1][j-1]-1,0))/2.0;
            }
        }
        // 查询的行不一定是最后一排的，也有可能是前面装满的
        return dp[query_row+1][query_glass+1]>=1?1:dp[query_row+1][query_glass+1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

背包DP

基础知识

二维01背包

这里主要是参考代码随想录的动态规划专题，主要涉及到了01背包和完全背包问题。

从01背包开始，首先定义了「二维的状态」dp[i][j]，代表从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

递推公式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

然后是dp数组「初始化」，dp[i][j] 与dp[i - 1][j]有关，因此需要先初始化dp[0][j]。dp[0][j]的初始化要采用倒序遍历，因为这样子可以保证物品0即使在背包容量很大，如bagWeight的时候，也只会被放入一次，因为前面的dp[0][j - weight[0]]还并没有放过该物品，符合01背包的定义，倒序遍历如下：

// 倒序遍历
for (int j = bagWeight; j >= weight[0]; j--) {
    dp[0][j] = dp[0][j - weight[0]] + value[0]; // 初始化i为0时候的情况
}
1
2
3
4

特别地，当用二维01背包去解决组合问题的时候，需要考虑$if(j<nums[i])$的连续性问题，需要将不考虑$nums[i]$的方案数放进来。而变成一维01背包的时候，由于数组的复制，不需要额外去考虑连续性。

1. 对于「两层for循环顺序」，先遍历物品还是先遍历背包重量都可以，和递推的方向和本质有关，dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的，他们都在dp[i][j]的左上方，在不同的遍历顺序下都能推导出来。

2. 对于「背包容量的遍历顺序」，都可以，$dp[0][j]$已经初始化出来，同时因为$dp[i-1][j-weight[i]]$上一层状态已经计算好。

先遍历物品的代码：

//先遍历物品嵌套遍历背包
for(int i = 1; i < weight.length; i++) { // 遍历物品
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量 
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 需要考虑连续性
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        
    }
}
1
2
3
4
5
6
7
8

对于其中两层循环物理意义的理解，凭空想来不知道究竟应该放哪些物品，但是将问题转换一下，物品已经全部摆在那里，取决于我们究竟取什么。因此对于物品，外循环从前往后每次固定一个，然后内循环用这个物品重量进行更新（如果是一维的就必须倒序），每种物品依次更新，相当于就是用前面物品的价值结果尝试腾空间给新的物品（比如$dp[i-1][j-weight[i]]$），让他的价值最大化。

先遍历背包重量的代码：

// 先遍历背包嵌套遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.length; i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 需要考虑连续性，选不了就是没选的价值
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}
1
2
3
4
5
6
7

一维01背包

进一步地是二维dp转为一维dp，在解题过程中我们常采用这种，可以将一维数组理解成一个滚动数组，在每轮更新dp[j]的时候，上一轮的dp[j]值可以在当前层继续利用。

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

递推公式为dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

初始化dp数组全为0（需要根据题目要求灵活设定）.

1. 对于「背包容量的遍历顺序」，一定是「倒序遍历」的，这是为了保证物品只被放入一次，这和上面二维的初始化是统一的。可以这样理解：先写一下dp是二维数组的解法，外层循环物品，内层循环背包容量，会发现二维数组的解法中，$dp[i][j]$其实是由其左上方和上方决定的，然后一维数组其实就是相当于每次i开始新的循环都把上一行直接复制黏贴到下一行，再在原有的基础上做改动，也就上方的状态通过改成一维数组不用考虑了；但是左方不能被更早的修改，因为行内的元素在求出新的值之前，是被当成二维数组中上一行的元素在使用的，所以如果提前计算了左方，左边的元素就不再代表原先二维数组中的左上方的值了。

2. 对于「两层for循环顺序」，一维01背包中 ，由于是倒序遍历背包容量，必须先遍历物品再嵌套遍历背包容量，先遍历物品可以理解为每次固定了一个新的物品，滚动数组dp[j]可以记录下每轮物品下（全部轮过去就是所有物品都试过了），相同容量的最大化价值。如果先遍历背包容量，会使得在每个背包容量下，第一轮只放下背包能容纳的价值最高的一个物品（并没有考虑空间和价值），然后在此基础上继续放是不合理的。不同于二维01背包的「两层for循环顺序」没有要求，因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖。

// 相比于二维dp，滚动数组直接复用了上一轮i-1的结果，循环还是两层
for(int i = 0; i < weight.length; i++) { // 遍历物品
	// 从大到小倒序遍历背包容量
	// 最小值weight[i]，由于是复制因此不需要考虑连续性
    for(int j = bagWeight; j >= weight[i]; j--) { 
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);

    }
}
1
2
3
4
5
6
7
8
9

完全背包

在一维的情况下，完全背包和01背包问题唯一不同的地方就是，「每种物品可以放无限次」，唯一区别体现在「背包容量的遍历顺序」，01背包的核心代码如下，内嵌的背包容量循环是倒序遍历，为了保证每个物品仅被添加一次。

for(int i = 0; i < weight.length; i++) { // 遍历物品
	// 从大到小倒序遍历背包容量，最小值weight[i]，到下面就没有更新价值
    for(int j = bagWeight; j >= weight[i]; j--) { 
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
1
2
3
4
5
6

1. 对于「背包容量的遍历顺序」，是正序遍历，因为完全背包的物品可以添加多次，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.length; i++) { // 遍历物品
	// 从小到大遍历背包容量，最小值weight[i]，到下面就没有更新价值
    for(int j = weight[i]; j < bagWeight ; j++) { 
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);

    }
}
1
2
3
4
5
6
7
8

2. 对于「两层for循环顺序」，纯完全背包求得是能否凑成总和，和凑成总和的元素顺序没有关系；而当求方案数的时候，需要区分是不考虑顺序的完全背包组合问题，还是考虑顺序的完全背包排列问题。不考虑顺序的完全背包组合问题，先遍历物品再嵌套遍历背包容量，因为外层循环相当于定下了物品的顺序，只考虑了一种情况。考虑顺序的完全背包排列问题，先遍历背包容量然后遍历物品，每个容量都考虑了用上每个物品可能的方案数$dp[j-coins[i]]$，将他们求和。

综上所述，背包问题基本上都是先遍历物品再遍历背包容量，在一维状态的定义和初始化上也一致，重点关注「背包容量的遍历顺序」在01背包和完全背包上的不同。

这位大佬的总结很好：

首先是背包分类的模板：
1、0/1背包：外循环nums, 内循环bagWeight, bagWeight倒序且bagWeight>=nums[i];
2、完全背包：外循环nums, 内循环bagWeight, bagWeight正序且bagWeight>=nums[i];
3、排列背包：外循环bagWeight, 内循环nums, bagWeight正序且bagWeight>=nums[i] (背包中的物品要考虑顺序);
4、分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板

然后是问题分类的模板：
1、最值问题: dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);
2、存在问题：dp[i]=dp[i]||dp[i-num];
3、组合个数问题：dp[i]+=dp[i-num];

相关题目

心得体会：

1. 需要根据背包问题进行灵活转化，即在一个固定容量内进行各种物品填充，结果可能是求最大值或者是最小值，对应的初始化数据也得看是小是大，且每个位置初始化数据不一定相同。

416.分割等和子集

01背包问题，有点夹逼的思想在里面，找到和的一半作为背包容量，往里面放数，一个数字的价值和其大小1:1。$dp[j]$代表目标和为j时，能够凑出的最大和，极限情况下能找到的话肯定$dp[bag]==bag$，也就是刚好分割了等和子集。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int n:nums){
            sum+=n;
        }
        if(sum%2!=0) return false;
        int bag=sum/2;
        int[]dp=new int[bag+1];
        for(int i=0;i<nums.length;i++){
            for(int j=bag;j>=nums[i];j--){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[bag]==bag;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二维的正确写法，先从上往下循环物品，然后从右往左循环背包容量，仍然和左上角数据有关，并且已经先横向更新了

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int n:nums){
            sum+=n;
        }
        if(sum%2!=0) return false;
        int target=sum/2;
        int len=nums.length;
        int[][]dp=new int[len][target+1];
        for(int j=target;j>=nums[0];j--){
            dp[0][j]=dp[0][j-nums[0]]+nums[0];
        }
        for(int i=1;i<len;i++){
            for(int j=target;j>=0;j--){
                if(j>=nums[i])dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);              else dp[i][j]=dp[i-1][j];
            }
        }
        // for(int i=0;i<len;i++){
        //     for(int j=0;j<=target;j++){
        //         System.out.print(dp[i][j]+" ");
        //     }
        //     System.out.println();
        // }
        return dp[len-1][target]==target;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

二维的错误写法，循环调换顺序：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int n:nums){
            sum+=n;
        }
        if(sum%2!=0) return false;
        int target=sum/2;
        int len=nums.length;
        int[][]dp=new int[len][target+1];
        for(int j=target;j>=nums[0];j--){
            dp[0][j]=dp[0][j-nums[0]]+nums[0];
        }
        for(int j=target;j>=0;j--){
            for(int i=1;i<len;i++){
                if(j>=nums[i])dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);              else dp[i][j]=dp[i-1][j];
            }// 和左上角有关，从右往左，从下往上进行更新，左上角还没更新
        }
        for(int i=0;i<len;i++){
            for(int j=0;j<=target;j++){
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        return dp[len-1][target]==target;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

1049.最后一块石头的重量II

01背包问题，把问题当成分成两大堆石头，$dp[j]$代表目标重量为j时，能够凑出的最大重量，最终他们的差距为$sum-2\ast dp[bag]$。

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int s:stones){
            sum+=s;
        }
        int target=sum/2;
        int[]dp=new int[target+1];
        int len=stones.length;
        // for(int j=target;j>=stones[0];j--){
        //     dp[j]=dp[j-stones[0]]+stones[0];
        // }

        for(int i=0;i<len;i++){
            for(int j=target;j>=stones[i];j--){ // j<stones[i]的直接延续上面的
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

二维的写法：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int s:stones){
            sum+=s;
        }
        int target=sum/2;
        int len=stones.length;
        int[][]dp=new int[len][target+1];
        for(int j=target;j>=stones[0];j--){
            dp[0][j]=dp[0][j-stones[0]]+stones[0];
        }
        for(int i=1;i<len;i++){
            for(int j=target;j>=0;j--){
                if(j>=stones[i]) dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);
                else dp[i][j]=dp[i-1][j];
            }
        }
        return sum-2*dp[len-1][target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

494.目标和

01背包组合问题，参考官方题解，能够将neg抽象成背包容量的思想很巧妙。

二维dp的解法：
$dp[i+1][j]$代表在选择下标为[0,i]的nums去组合结果j时，总共的组合数

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //(sum-neg)-neg=target
        int sum=0;
        for(int n:nums){
            sum+=n;
        }
        // 必须保证neg为偶数且sum-target>=0
        if(target>sum||(sum-target)%2==1) return 0;
        int neg=(sum-target)/2;
        int len=nums.length;
        // dp[i+1][j]代表在选择下标为[0,i]的nums去组合结果j时，总共的组合数
        int[][]dp=new int[len+1][neg+1];
        // 由于是方法数，作为最小单元必须为1
        dp[0][0]=1;
        for(int i=0;i<nums.length;i++){
            for(int j=neg;j>=0;j--){
                // 用上nums[i]和不用上nums[i]的两种组合策略加起来
                if(j>=nums[i])dp[i+1][j]=dp[i][j]+dp[i][j-nums[i]];
                // 只能不用上nums[i]
                else dp[i+1][j]=dp[i][j];
            }
        }
        return dp[len][neg];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

改造成一维dp滚动数组：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //(sum-neg)-neg=target
        int sum=0;
        for(int n:nums){
            sum+=n;
        }
        // 必须保证neg为偶数且sum-target>=0
        if(target>sum||(sum-target)%2==1) return 0;
        int neg=(sum-target)/2;
        int len=nums.length;
        // dp[j]代表去组合结果j时，总共的组合数
        int[]dp=new int[neg+1];
        dp[0]=1;
        for(int i=0;i<nums.length;i++){
            for(int j=neg;j>=0;j--){
                // 用上nums[i]和不用上nums[i]的两种组合策略加起来
                if(j>=nums[i])dp[j]=dp[j]+dp[j-nums[i]];
            }
        }
        return dp[neg];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

474.一和零

01背包问题，strs中的字符串只能取一次，遍历所有strs更新所有状态。$dp[i][j]$代表有i个0，n个1时当前最大子集的长度。

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // dp[i][j]代表有i个0，n个1时最大子集的长度
        int[][]dp=new int[m+1][n+1];
        // 遍历所有strs
        for(String s:strs){
            int zero=0;
            int one=0;
            for(char c:s.toCharArray()){
                if(c=='0') zero++;
                else one++;
            }
            // 必须两个维度倒序
            for(int i=m;i>=zero;i--){
                for(int j=n;j>=one;j--){
                    dp[i][j]=Math.max(dp[i][j],dp[i-zero][j-one]+1);
                }
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

打印前两次输出：

322.零钱兑换

完全背包问题，求的是在指定容量内放无限次物品，所需要的最少物品数目。$dp[i]$表示要达到重量为i时，最少的硬币个数.

class Solution {
    public int coinChange(int[] coins, int amount) {
        //dp[i]表示要达到重量为i时，最少的硬币个数
        int[]dp=new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        int len=coins.length;
        dp[0]=0;
        for(int i=0;i<len;i++){
            for(int j=0;j<=amount;j++){
                if(j>=coins[i]&&dp[j-coins[i]]!=Integer.MAX_VALUE) dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

518.零钱兑换2

完全背包组合问题，不需要考虑选择硬币的顺序，参考carl的题解，二维dp: $dp[i+1][j]$代表用下标[0,i]的硬币去构成总金额j的方法数。

class Solution {
    public int change(int amount, int[] coins) {
        int len=coins.length;
        // dp[i+1][j]代表用下标[0,i]的硬币去构成总金额j的方法数
        int[][]dp=new int[len+1][amount+1];
        dp[0][0]=1;
        for(int i=0;i<len;i++){
            for(int j=0;j<=amount;j++){
                // 能够用上coins[i]
                if(j>=coins[i]){
                    dp[i+1][j]=dp[i][j];
                    // 可以用上多次
                    for(int k=1;k*coins[i]<=j;k++){
                        dp[i+1][j]+=dp[i][j-k*coins[i]];
                    }
                }
                // 用不上coins[i]
                else dp[i+1][j]=dp[i][j];
            }
        }
        return dp[len][amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

一维滚动数组dp:

class Solution {
    public int change(int amount, int[] coins) {
        int len=coins.length;
        // dp[j]代表用硬币去构成总金额j的方法数
        int[]dp=new int[amount+1];
        dp[0]=1;
        for(int i=0;i<len;i++){
            for(int j=1;j<=amount;j++){
                // 能够用上coins[i]
                if(j>=coins[i]){
                    dp[j]+=dp[j-coins[i]];
                }
            }
        }
        return dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

377.组合总和Ⅳ

完全背包的排列问题，类似零钱兑换，但是这里要考虑的是排列方案数，因此背包重量内部嵌套物品。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // dp[i]代表组成目标i的元素组合个数
        int[]dp=new int[target+1];
        int len=nums.length;
        // 方案的初始化不要忘记
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(int j=0;j<len;j++){
                if(i>=nums[j]){
                    dp[i]+=dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

279.完全平方数

完全背包的最小值问题，$dp[i]$代表要组成i所需要的最少完全数，物品为$i\ast i<=n$的$i$。

class Solution {
    public int numSquares(int n) {
    	// dp[i]代表要组成i所需要的最少完全数
        int[]dp=new int[n+1];
        Arrays.fill(dp,0x3f3f3f3f);
        dp[0]=0;
        for(int i=1;i*i<=n;i++){
            for(int j=0;j<=n;j++){
                // 选或者不选
                if(j>=i*i) dp[j]=Math.min(dp[j-i*i]+1,dp[j]);
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

139.单词拆分

完全背包的存在问题，$dp[i+1]$代表以下标i结尾的s是否能由wordDict拼接出来

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len=s.length();
        // dp[i+1]代表以下标i结尾的s是否能由wordDict拼接出来
        boolean[]dp=new boolean[len+1];
        // dp[0]为true
        dp[0]=true;
        for(int i=1;i<=len;i++){
            for(int j=0;j<i;j++){
            	// s.substring(j,i))和dp[j]的j之间指代的关系差1
                if(wordDict.contains(s.substring(j,i))&&dp[j]){
                    dp[i]|=true;
                }
            }
        }
        return dp[len];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

或者复习下和动态规划思想相似的记忆化搜索DFS：

class Solution {
    int[]cache;
    public boolean wordBreak(String s, List<String> wordDict) {
        int len=s.length();
        cache=new int[len+1];
        return canBreak(0,s,wordDict);
    }

    // 从startIndex开始（包括）是否可以拼接出单词
    public boolean canBreak(int startIndex, String s, List<String> wordDict){
        if(startIndex==s.length()) return true;
        // 记忆化直接返回cache[startIndex]
        if(cache[startIndex]!=0) return cache[startIndex]==1?true:false;
        for(int i=startIndex+1;i<=s.length();i++){
            String split=s.substring(startIndex,i);
            if(wordDict.contains(split)&&canBreak(i,s,wordDict)){
                cache[startIndex]=1;
                return true;
            }
        }
        cache[startIndex]=-1;
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

序列DP

序列问题是DP中很典型的问题，常常定义$dp[i]$和$dp[i][j]$这样的状态。

• 其中下标i代表的字符是否需要严格包括在$dp[i]$中，是需要根据题目变换的，比如53.最大子数组和就是要严格考虑nums[i]的最大子数组和，而392.判断子序列中$dp[i+1][j+1]$代表以下标i结尾的s和以j结尾的t（具有状态延续性，不一定非得考虑i,j，主要看不相等如何处理）的最长公共子序列长度，记录状态的信息不同，前面状态提供给后面状态的信息也不同。

• 同时字符对象数目也不同，会出现针对一个字符串求最值或者两个字符串求公共序列的分别。

940.不同的子序列2

参考宫水三叶的题解，子序列的问题仍然以dp[i]表示考虑前i个字符的情况，不过会增加一个纬度的信息来应对不同题目，这里是增加以某个单词结尾的信息，$dp[i][j]$表示前i个字符在以字母j结尾的情况下，能够组成的不同的子序列。递推公式如何更新我思考了好久，可以这么理解，在遍历整个字符串s的过程中，更新每个dp[i]的26种状态，分为两种情况。（1）当前字符不是状态更新中的结尾字符，则沿用前面的状态。（2）当前字符是状态更新中的结尾字符，则需要将该字符结尾的个数进行更新，就是单独做一个+前面所有字符结尾的和。

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod=1e9+7
        dp=[[0]*26 for _ in range(1+len(s))]
        for i,c in enumerate(s,1):
            gap=ord(s[i-1])-ord('a')
            for j in range(26):
                if j!=gap:
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=(1+sum(dp[i-1]))%mod
        return int(sum(dp[i])%mod)
1
2
3
4
5
6
7
8
9
10
11
12

300.最长递增子序列

非连续的序列DP问题，dp[i]表示以nums[i]结尾（包括nums[i]）的最长递增子序列长度，时间复杂$O(N^2)$. dp[i]只记录最大长度，然后从前往后推导就能够不断地累加到最大长度。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        int[]dp=new int[len];
        int ans=1;
        Arrays.fill(dp,1);
        for(int i=0;i<len;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                    ans=Math.max(ans,dp[i]);
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这题的二分查找优化做法：参考题解，相当于做N次查找，查找大于等于某个数的最小值，相当于就是找那个牌堆顶比我大的最小值，放上去能尽可能保证牌堆变多。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        int[]s=new int[len];
        int piles=0;
        for(int i=0;i<len;i++){
            int left=0;
            int right=piles;
            while(left<right){
                int mid=(left+right)/2;
                if(s[mid]>=nums[i]){
                    right=mid;
                }else{
                    left=mid+1;
                }
            }
            // 先堆数++，然后存数
            if(left==piles)piles++;
            s[left]=nums[i];
        }
        return piles;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

674.最长连续递增序列

连续的序列dp问题，当碰到不是连续增长的就不更新$dp[i]$，$dp[i]$表示以$nums[i]$（严格包括）结尾的最长连续递增序列长度。

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int len=nums.length;
        int[]dp=new int[len];
        Arrays.fill(dp,1);
        int ans=1;
        for(int i=1;i<len;i++){
            if(nums[i]>nums[i-1]){
                dp[i]=dp[i-1]+1;
            }
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

或者直接贪心做法，拿一个变量记录当前遇到的最大值

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans=1;
        int res=1;
        for(int i=1;i<nums.length;i++){
           if(nums[i]>nums[i-1]) res++;
           else res=1;
           ans=Math.max(ans,res);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

718.最长重复子数组

连续序列dp，二维，dp[i+1][j+1]代表以下标i结尾的A和以下标j结尾的B（严格包括下标i和下标j）中，最长重复子数组的长度，留外圈的padding方便统一递推。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int ans=0;
        int n1=nums1.length;
        int n2=nums2.length;
        int[][]dp=new int[n1+1][n2+1];
        for(int i=0;i<n1;i++){
            for(int j=0;j<n2;j++){
                if(nums1[i]==nums2[j]){
                	// 相等才来更新长度，否则默认为0
                    dp[i+1][j+1]=dp[i][j]+1;
                }
                ans=Math.max(ans,dp[i+1][j+1]);
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1143.最长公共子序列

不连续序列dp，二维，$dp[i+1][j+1]$代表以下标i结尾的text1和以j结尾的text2的最长公共子序列长度（不一定包括下标i和下标j），分为t1[i]、t2[j]相等和不相等两种情况考虑。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int ans=0;
        int n1=text1.length();
        int n2=text2.length();
        char[]t1=text1.toCharArray();
        char[]t2=text2.toCharArray();
        int[][]dp=new int[n1+1][n2+1];
        for(int i=0;i<n1;i++){
            for(int j=0;j<n2;j++){
                // 两个位置相同
                if(t1[i]==t2[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                }else{ // 两个位置不同
                    dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);
                }
                ans=Math.max(ans,dp[i+1][j+1]);
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1035.不相交的线

是上一题不连续的最长公共子序列一样的思想，不过需要一层抽象

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
         int ans=0;
        int n1=nums1.length;
        int n2=nums2.length;
        int[][]dp=new int[n1+1][n2+1];
        for(int i=0;i<n1;i++){
            for(int j=0;j<n2;j++){
                // 两个位置相同
                if(nums1[i]==nums2[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                }else{ // 两个位置不同
                    dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);
                }
                ans=Math.max(ans,dp[i+1][j+1]);
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

53.最大子数组和

线性序列dp，$dp[i]$表示包括下标i能够取到的最大连续子数组和，这里严格强调包括i是因为后面的序列题处理有些$dp[i]$并不严格包括$nums[i]$。

class Solution {
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        int ans=-0x3f3f3f3f;
        int[]dp=new int[n+1];
        for(int i=0;i<n;i++){
       		// 从i开始或者在之前的基础上继续递增
            dp[i+1]=Math.max(nums[i],dp[i]+nums[i]);
            ans=Math.max(ans,dp[i+1]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

或者直接贪心，只在之前的和<0的时候重新开始：

class Solution {
    public int maxSubArray(int[] nums) {
        int ans=-0x3f3f3f3f;
        int res=0;
        for(int i=0;i<nums.length;i++){
            // 之前的和小于零，置零然后从当前位置继续往后加
            if(res<0) res=0;
            res+=nums[i];
            ans=Math.max(ans,res);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

392.判断子序列

二维dp，编辑距离，用类似1143.最长公共子序列的思路求出最长匹配的长度，如果该长度能够等于s的长度，那就说明s可以是子序列，时间复杂度$O(M\ast N)$。

这里$dp[i+1][j+1]$代表以下标i结尾的s和以j结尾的t（不一定包括）的最长公共子序列长度，语义是并不要求公共子序列必须以cs1[i]、cs2[j]结尾，前面的最大公共长度可以延续过来，分为cs1[i]、cs2[j]相等和不相等两种情况考虑。

class Solution {
    public boolean isSubsequence(String s, String t) {
        char[] cs1=s.toCharArray();
        char[] cs2=t.toCharArray();
        int n1=cs1.length;
        int n2=cs2.length;
        int maxv=0;
        int[][]dp=new int[n1+1][n2+1];
        for(int i=0;i<n1;i++){
            for(int j=0;j<n2;j++){
                if(cs1[i]==cs2[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                }else{
                    dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);
                }
                maxv=Math.max(maxv,dp[i+1][j+1]);
            }
        }
        return maxv==n1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

或者直接双指针，判断是否能将cs1全部匹配完，时间复杂度$min(M,N)$

class Solution {
    public boolean isSubsequence(String s, String t) {
        char[] cs1=s.toCharArray();
        char[] cs2=t.toCharArray();
        int n1=cs1.length;
        int n2=cs2.length;
        int i=0,j=0;
        while(i<n1&&j<n2){
            if(cs1[i]==cs2[j]){
                i++;
                j++;
            }else{
                j++;
            }
        }
        // i匹配到底
        if(i==n1) return true;
        // j匹配到底，i没有匹配到底
        return false;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

115.不同的子序列

二维dp，编辑距离，$dp[i+1][j+1]$表示以$s[i]$和$t[j]$字符结尾（不一定包括）,s中出现t的个数，加外圈padding用于表示一方为空的情况。题目意思为在 s 串身上 “挑选” 字符，去匹配 t 串的字符，求挑选的方式数，考虑s[i]和t[j]间的相等关系。参考题解，动态规划和记忆化搜索间的本质是一样的，动态规划从大到小分析递推公式，从小（初始化）到大计算状态，记忆化搜索从大到小拆解，从小到大返回结果。

class Solution {
    public int numDistinct(String s, String t) {
        char[] cs1=s.toCharArray();
        char[] cs2=t.toCharArray();
        int n1=cs1.length;
        int n2=cs2.length;
        // dp[i][j]表示以s[i-1]和t[j-1]字符结尾,s中出现t的个数
        int[][] dp=new int[n1+1][n2+1];
        // 初始化很重要
        for(int i=0;i<=n1;i++){
            dp[i][0]=1;
        }
        for(int j=1;j<=n2;j++){
            dp[0][j]=0;
        }
        for(int i=0;i<n1;i++){
            for(int j=0;j<n2;j++){
                if(cs1[i]==cs2[j]){
                    dp[i+1][j+1]=dp[i][j]+dp[i][j+1];
                }else{
                    dp[i+1][j+1]=dp[i][j+1];
                }
            }
        }
        return dp[n1][n2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

583.两个字符串的删除操作

二维dp，编辑距离，dp[i+1][j+1]表示以s[i]和t[j]字符结尾（不一定包括）,要使他们相同需要删除的最小步数，加外圈padding用于表示一方为空的情况，这也是有实际意义的，就是一方和空比较需要删除的个数。

解这种题还是从当前s[i]和t[j]是否相等出发，重点看它和前面状态的关系，从大到小分析，从小（初始化）到大计算状态。

class Solution {
    public int minDistance(String word1, String word2) {
        char[] s1=word1.toCharArray();
        char[] s2=word2.toCharArray();
        int n1=s1.length;
        int n2=s2.length;
        int[][]dp=new int[n1+1][n2+1];
        for(int i=0;i<=n1;i++){
            dp[i][0]=i;
        }
        for(int i=0;i<=n2;i++){
            dp[0][i]=i;
        }
        for(int i=0;i<n1;i++){
            for(int j=0;j<n2;j++){
                if(s1[i]==s2[j]){
                    dp[i+1][j+1]=dp[i][j];
                }else{
                    dp[i+1][j+1]=Math.min(dp[i][j]+2,Math.min(dp[i+1][j]+1,dp[i][j+1]+1));
                }
            }
        }
        return dp[n1][n2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

72.编辑距离

二维dp，编辑距离，这题类似上面，$dp[i+1][j+1]$表示以$s[i]$和$t[j]$字符结尾（不一定包括）,要使他们相同需要操作的最小步数，只不过在比较$s[i]$和$t[j]$是否相等的时候，增加了几种可能的操作，所以状态转换可能不一样。

参考题解。改很好理解，而一方的增删有点难理解， dp[i][j-1] 表示word1前i个字符转换到word2前j-1个字符的距离，在此基础上，在word2后增加一个字符，word1前i个字符转换到word2前j个字符的距离为dp[i][j-1]+1 。这是word2增，等价于word1删。 同理，dp[i-1][j] + 1 是word1增，等价于word2删。图中红色描绘的是$dp[i][j]$和$dp[i-1][j]$之间的关系，word1当前为h增加一个r，和word2中的r进行匹配，转换为word1为空" "（$dp[i-1][j]$为1相当于删掉h的空和r进行匹配）和word2中的r进行匹配再加上1，结果为2。感性理解就是既要删掉h又要增加r，只是不太理解为什么要保证每步操作完的字符串完全一致，应该和dp定义有关。

class Solution {
    public int minDistance(String word1, String word2) {
        char[]s1=word1.toCharArray();
        char[]s2=word2.toCharArray();
        int n1=s1.length;
        int n2=s2.length;
        int[][]dp=new int[n1+1][n2+1];
        // 初始化
        for(int i=0;i<=n1;i++){
            dp[i][0]=i;
        }
        for(int j=0;j<=n2;j++){
            dp[0][j]=j;
        }
        // 记录最小操作状态
        for(int i=0;i<n1;i++){
            for(int j=0;j<n2;j++){
                if(s1[i]==s2[j]){
                    dp[i+1][j+1]=dp[i][j];
                }else{
                    dp[i+1][j+1]=Math.min(dp[i][j]+1,Math.min(dp[i][j+1]+1,dp[i+1][j]+1));
                }
            }
        }
        return dp[n1][n2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

647.回文子串个数

二维dp，不能修改，求回文子串个数，$dp[i][j]$代表从下标i到下标j的子串是否是回文子串（严格包括），通过ans记录个数。其中状态的更新需要从下往上，这样子$dp[i][j]$才可以利用上$dp[i+1][j-1]$的结果。

class Solution {
    public int countSubstrings(String s) {
        int ans=0;
        int len=s.length();
        boolean[][]dp=new boolean[len][len];
        // 状态更新从下往上
        for(int i=len-1;i>=0;i--){
            for(int j=len-1;j>=i;j--){
                if(i==j){
                    dp[i][j]=true;
                }else if(j==i+1){
                    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]) ans++;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.最长回文子串

二维dp，不能修改，求最长回文子串，思路仍然是$dp[i][j]$代表从下标i到下标j的子串是否是回文子串（严格包括）,通过ans记录最大长度，start，end记录字符串开始结尾。注意状态方程用到的前一个状态是dp[i+1][j-1]。

class Solution {
    public String longestPalindrome(String s) {
        char[]cs=s.toCharArray();
        int len=cs.length;
        boolean[][]dp=new boolean[len][len];
        int start=-1;
        int end=-1;
        int ans=1;
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                if(cs[i]==cs[j]&&(j-i<2||dp[i+1][j-1])){
                    dp[i][j]=true;
                }
                // 记录最大长度和字符串开始start与结尾end
                if(dp[i][j]){
                    int temp=j-i+1;
                    if(temp>=ans){
                        ans=temp;
                        start=i;
                        end=j;
                    }
                }
            }
        }
        return s.substring(start,end+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

516.最长回文子序列

二维dp，可以删除，得到回文子序列的最大长度，$dp[i][j]$代表从下标i到下标j（不一定包括）中能够删除字符得到的最长子序列长度。其中特别注意后面的递推公式要用到前面的状态，内循环要从左到右。

class Solution {
    public int longestPalindromeSubseq(String s) {
        int len=s.length();
        int ans=1;
        int[][] dp=new int[len][len];
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){ // 内层循环从左到右
                if(s.charAt(i)==s.charAt(j)){
                    if(i==j) dp[i][j]=1;
                    else if(j==i+1) dp[i][j]=2;
                    else dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    if(j==i+1) dp[i][j]=1;
                    else dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]); // 这里需要用到左侧的结果
                }
                ans=Math.max(ans,dp[i][j]);
            }
        }
        return ans;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

上面的解法是从s.charAt(i)==s.charAt(j)出发进行区分，下面的解法是从[i,j]的区间长度出发进行区分。

class Solution {
    public int longestPalindromeSubseq(String s) {
        char[]cs=s.toCharArray();
        int len=s.length();
        int[][]dp=new int[len][len];
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                if(i==j) dp[i][j]=1;
                else if(j==i+1){
                    if(cs[i]==cs[j]) dp[i][j]=2;
                    else dp[i][j]=1;// 当两者不相等的时候，单独一个至少为1
                }else{
                    if(cs[i]==cs[j]) dp[i][j]=dp[i+1][j-1]+2;
                    else dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

132.分割回文串II

一维序列dp，可以看成是最长递增子序列和判断回文子串个数的综合。$dp[i]$表示以下标i结尾（包括i）的子串中符合要求的最小分割数。需要用到某个区间是否为回文串的结论，因此可以先进行预处理。

class Solution {
    public int minCut(String s) {
        char[]sc=s.toCharArray();
        int len=sc.length;
        int[]dp=new int[len];
        // 初始化为最大值
        Arrays.fill(dp,0x3f3f3f3f);
        boolean[][]f=huiWen(s);
        int ans=0;
        // 下面类似最长递增子序列
        for(int i=0;i<len;i++){
        	// [0,i]已经是回文串了，则分割数是0
            if(f[0][i]){
                dp[i]=0;
                continue;
            } 
            // 否则尝试分割
            for(int j=0;j<i;j++){
                if(f[j+1][i]) dp[i]=Math.min(dp[i],dp[j]+1);
            } 
        }
        return dp[len-1];
    }


    // 回文判断预处理
    public boolean[][] huiWen(String s){
        char[]sc=s.toCharArray();
        int len=sc.length;
        boolean [][] dp=new boolean[len][len];
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                if(sc[i]==sc[j]&&(j-i<2||dp[i+1][j-1])){
                    dp[i][j]=true;
                }
            }
        }
        return dp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

32.最长有效括号

$dp[i]$代表以s1[i]结尾（严格包括）的最长有效括号长度，$dp[i]$和前一个子问题的末尾$s[i-1]$的符号有关，需要从前往后进行递推。参考笨猪爆破组的题解.

class Solution {
    public int longestValidParentheses(String s) {
        char[] s1=s.toCharArray();
        int len=s1.length;
        // dp[i]代表以s1[i]结尾（严格包括）的最长有效括号长度
        int []dp=new int[len];
        int ans=0;
        for(int i=0;i<len;i++){
            if(s1[i]=='('){
                dp[i]=0;
            }else{
                // 当只有两个元素时
                if(i==1&&s1[i-1]=='('){
                    dp[i]=2;
                } // 当元素大于2时
                else if(i>1&&s1[i-1]=='('){
                    dp[i]=dp[i-2]+2;
                }
                else if(i>=1&&s1[i-1]==')'){
                    // 当远处存在一个有效括号且前面没有别的有效括号时 "(()())"
                    if(i-1-dp[i-1]==0&&s1[i-1-dp[i-1]]=='('){
                        dp[i]=dp[i-1]+2;
                    } //当远处存在一个有效括号且前面还有别的有效括号时  "()(())"
                    if(i-1-dp[i-1]>0&&s1[i-1-dp[i-1]]=='('){
                        dp[i]=dp[i-2-dp[i-1]]+dp[i-1]+2;
                    }
                }
            }
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

栈的做法是括号问题最常见的解决办法，参考笨猪爆破组的题解，其中设置参照点的思想值得学习。两种索引会入栈: 1.等待被匹配的左括号索引。2.充当「参照物」的右括号索引，当左括号匹配光时，栈需要留一个垫底的参照物，用于计算一段连续的有效长度。

class Solution {
    public int longestValidParentheses(String s) {
        char[] s1=s.toCharArray();
        int len=s1.length;
        Stack<Integer> st=new Stack<>();
        st.push(-1);
        int ans=0;
        for(int i=0;i<len;i++){
            if(s1[i]=='('){
                st.push(i);
            }else{
                st.pop(); // 先弹栈再计算
                if(st.isEmpty()){
                    st.push(i);
                }else{
                    // 当前下标减去栈顶下标
                    ans=Math.max(ans,i-st.peek());
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

96.字符串交织

参考题解，$dp[i+1][j+1]$代表以下标i结尾的s1和以下标j结尾的s2（严格包括）能否构成s3。

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1=s1.length();
        int len2=s2.length();
        int len3=s3.length();
        if(len1+len2!=len3) return false;
        boolean[][] dp=new boolean[len1+1][len2+1];
        dp[0][0]=true;
        for(int i=0;i<len1;i++){
            dp[i+1][0]=dp[i][0]&&s1.charAt(i)==s3.charAt(i);
        }
        for(int j=0;j<len2;j++){
            dp[0][j+1]=dp[0][j]&&s2.charAt(j)==s3.charAt(j);
        }
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                dp[i+1][j+1]=(dp[i][j+1]&&s1.charAt(i)==s3.charAt(i+j+1))||
                (dp[i+1][j]&&s2.charAt(j)==s3.charAt(i+j+1));
            }
        }
        return dp[len1][len2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

区间DP

状压DP

状态DP

状态DP的要点就是找出当前的状态定义
买卖股票问题：
第一眼单纯盯着价格，想找到最小价格和最大价格之间的差价，但是随着后面条件的限制以及时间复杂度的限制，单纯的暴力法就没办法解决了。于是将股票持有以及未持有的状态抽象出来，赋值为该状态下的持有现金。

121.买卖股票的最佳时机

先是一种极为简单的贪心做法，不要将自己的思维局限在dp

class Solution {
    public int maxProfit(int[] prices) {
        int minv=0x3f3f3f3f;
        int ans=0;
        for(int i:prices){
            minv=Math.min(minv,i); // 记录最小
            ans=Math.max(ans,i-minv); // 取最大
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11

接下来就是dp的定义，dp[i][1]代表第i天结算后持有股票的最大现金，dp[i][0]代表第i天结算后不持有股票的最大现金，现金不同于利润，花出去多少就是减去多少，卖掉多少就是加上多少，刚开始手上的现金为0，可以负债。

class Solution {
    public int maxProfit(int[] prices) {
        int maxv=0;
        int len=prices.length;
        int[][] dp=new int[len][2]; // 第i天收盘手上有的钱
        dp[0][0]=0; // 不持有股票
        dp[0][1]=-prices[0]; // 持有股票
        for(int i=1;i<len;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
        }
        return dp[len-1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

由于状态只与前一天的状态有关，可以采用滚动数组的方式优化空间，空间直接打到O(1)

122.买卖股票的最佳时机II

同样可以使用贪心和滚动数组，这里只给出dp，不区分是第几次买入股票

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp=new int[2][2];
        dp[0][0]=0; //不持有股票
        dp[0][1]=-prices[0]; //持有股票
        int len=prices.length;
        for(int i=1;i<len;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],dp[(i-1)%2][0]-prices[i]);
        }
        return dp[(len-1)%2][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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

class Solution {
    public int maxProfit(int[] prices) {
        int len=prices.length;
        int[][]dp=new int[len][5];
        // 0.没有操作
        // 1.第一次买入
        // 2.第一次卖出
        // 3.第二次买入
        // 4.第二次卖出
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        dp[0][2]=0; // 买入又卖出
        dp[0][3]=-prices[0]; // 买入又卖出又买入
        for(int i=1;i<len;i++){
            dp[i][0]=dp[i-1][0];
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            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 dp[len-1][4];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

class Solution {
    public int maxProfit(int k, int[] prices) {
        int len=prices.length;
        int[][]dp=new int[len][2*k+1];
        for(int i=0;i<2*k+1;i++){
            if(i%2==1){
                dp[0][i]=-prices[0]; // 奇数是买入的状态
            }
        }
        for(int i=1;i<len;i++){
            dp[i][0]=dp[i-1][0];
            for(int j=1;j<2*k+1;j++){
                if(j%2==0){
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
                }
            }
        }
        return dp[len-1][2*k];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

309.最佳买卖股票时机含冷冻期

将冷冻期的状态算进去

class Solution {
    public int maxProfit(int[] prices) {
        int len=prices.length;
        int[][]dp=new int[len][4];
        // 0：买入股票状态
        // 1：当天卖出股票状态
        // 2：冰冻期状态
        // 3：冰冻期两天后可以买入的状态，但还没买
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        dp[0][2]=0;
        dp[0][3]=0;
        for(int i=1;i<len;i++){
            dp[i][0]=Math.max(dp[i-1][0],Math.max(dp[i-1][3]-prices[i],dp[i-1][2]-prices[i])); // 这里状态别少
            dp[i][1]=dp[i-1][0]+prices[i];
            dp[i][2]=dp[i-1][1];
            dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]);
        }
        return Math.max(dp[len-1][1],Math.max(dp[len-1][2],dp[len-1][3]));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

714.买卖股票的最佳时机含手续费

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int len=prices.length;
        int[][] dp=new int[len][2]; // 只需要关注持有不持有的问题
        dp[0][0]=0;
        dp[0][1]=-prices[0]; 
        for(int i=1;i<len;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee); //相比于第二题加个手续费
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            System.out.println( dp[i][0]+" "+ dp[i][1]);
        }
        return dp[len-1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

打家劫舍：
也是要发现前后状态的联系

198.打家劫舍

二维dp

class Solution {
    public int rob(int[] nums) {
        int len=nums.length;
        int[][]dp=new int[len][2];
        // dp[i][0]代表第i间房子没有被小偷偷窃，得到的最高金额
        // dp[i][1]代表第i间房子被小偷偷窃，得到的最高金额
        dp[0][0]=0;
        dp[0][1]=nums[0];
        for(int i=1;i<len;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=dp[i-1][0]+nums[i];
        }
        return Math.max(dp[len-1][0],dp[len-1][1]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

一维dp，考虑偷与不偷的选择

class Solution {
    public int rob(int[] nums) {
        int len=nums.length;
        int[]dp=new int[len];
        dp[0]=nums[0];
        if(len==1) return dp[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<len;i++){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]); // 偷与不偷，考虑两种选择，但不代表两种选择的dp代表的都是偷
        }
        return dp[len-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

数位DP

树形DP