背包问题

有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

背包最大重量为4。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

二维dp数组01背包

1.确定dp数组以及下标的含义：dp[i] [j]表示从下标为[0 - i]的物品里任意取物品，放进容量为j的背包中，价值总和的最大值。

2.确定递推公式：

• **不放物品i：**由dp[i - 1] [j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i] [j]就是dp[i - 1] [j]。（其实就是物品i的重量大于背包j的重量，物品i无法放进背包中，所以背包内的价值依然和前面相同）
• **放物品i：**由dp[i - 1] [j - weight[i]]推出，dp[i - 1] [j - weight[i]]为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1] [j - weight[i]] + value[i]（物品i的价值），就是背包放物品i得到的最大价值

递推公式：dp[i] [j] = Math.max(dp[i - 1] [j],dp[i - 1] [j - weight[i]] + value[i])

3.dp数组如何初始化：

从dp[i] [j]的定义出发，如果背包容量j为0的话，即dp[i] [0]，无论是选取哪些物品，背包价值总和一定为0。

因为递推公式中i是由i - 1推导出来的，那么i为0的时候就一定要初始化。

dp[0] [j]，即i为0时，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。显然当j < weight[0]时,dp[0] [j]应该是0，因为背包容量比编号0的物品重量还小。当j >= weight[0]时，dp[i] [j]应该是value[0]，因为背包容量足够存放编号0的物品。

for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

因为dp[i] [j]是由左上方的数值推导出来的，所以其它下标可以初始为任何数值，因为都会被覆盖。

4.确定遍历顺序：

先遍历物品后遍历背包

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

先遍历背包后遍历物品

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

完整代码：

public static void main(String[] args) {
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagsize = 4;
    testweightbagproblem(weight, value, bagsize);
}
public static void testweightbagproblem(int[] weight, int[] value, int bagsize) {
    //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
    int[][] dp = new int[weight.length][bagsize + 1];
    //初始化
    for (int j = weight[0]; j <= bagsize; j++) {
        dp[0][j] = value[0];
    }
    //先遍历物品后遍历背包
    for (int i = 1; i < weight.length; i++) {
        for (int j = 0; j <= bagsize; 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]);
        }
    }
    //打印dp数组
    for (int i = 0; i < weight.length; i++) {
        for (int j = 0; j <= bagsize; j++) {
            System.out.print(dp[i][j] + " ");
        }
        System.out.print("\n");
    }
}

一维dp数组（滚动数组）

1.确定dp数组的定义：

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

2.一维dp数组的递推公式：

dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。dp[j - weight[i]] + value[i]表示容量为j - 物品i重量的背包加上物品i的价值。（也就是容量为j的背包，放入了物品i之后的价值，即dp[j]）

此时dp[j]有两个选择，一个是取自己dp[j]相当于二维dp数组中的dp[i-1] [j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，需要选择两者之中的最大值。

**递推公式：**dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);

3.一维dp数组初始化

dp[j]表示容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

由递推公式可知dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数，那么非0下标都初始化为0就可以了。这样才能让dp数组在递推公式的过程中取得最大价值，而不是被初始值覆盖了。

4.一维dp数组遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

遍历背包时倒序遍历是为了保证物品i只被放入一次！一旦正序遍历了，那么物品0就会被重复加入多次！

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

为什么倒序遍历，就可以保证物品只放入一次呢？

倒序就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

为什么二维dp数组遍历的时候不用倒序呢？因为对于二维dp，dp[i] [j]都是通过上一层即dp[i - 1] [j]计算而来的，本层的dp[i] [j]并不会被覆盖！

一维dp数组的写法中，背包容量一定是要倒序遍历的，且要先遍历物品再遍历背包。（如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即背包里只放入了一个物品）。

5.举例推导dp数组：

完整代码：

public static void main(String[] args) {
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagsize = 4;
    testweightbagproblem(weight, value, bagsize);
}
public static void testweightbagproblem1(int[] weight, int[] value, int bagsize) {
    //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
    int[] dp = new int[bagsize + 1];
    //遍历顺序：先遍历物品再遍历背包
    for(int i = 0; i < weight.length; i++) {
        for(int j = bagsize; j >= weight[i]; j--) {
            dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);
        }
    }
    //打印dp数组
    for (int j = 0; j <= bagsize; j++){
        System.out.print(dp[j] + " ");
    }
}

完全背包

有N件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品都有无限个(也就是可以放入背包多次)，求解将哪些物品装入背包里物品价值总和最大。完全背包和01背包问题唯一不同的地方就是每种物品都有无限件。

//先遍历物品，再遍历背包
private static void testCompletePack(){
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for(int i = 0; i < weight.length; i++) {
        for(int j = weight[i]; j <= bagWeight; j++) {
            dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);
        }
    }
    for (int maxValue : dp){
        System.out.println(maxValue + "   ");
    }
}

//先遍历背包，再遍历物品
private static void testCompletePackAnotherWay(){
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量
        for (int j = 0; j < weight.length; j++){ // 遍历物品
            if (i - weight[j] >= 0){
                dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
            }
        }
    }
    for (int maxValue : dp){
        System.out.println(maxValue + "   ");
    }
}

多重背包

有N种物品和一个容量为V的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci，价值是Wi。求解将哪些物品装入背包可使这些物品耗费的空间总和不超过背包容量且价值总和最大。

背包最大重量为10。

物品为：

重量	价值	数量
物品0	1	15	2
物品1	3	20	3
物品2	4	30	2

问背包能背的物品最大价值是多少？

和如下情况有区别么？

重量	价值	数量
物品0	1	15	1
物品0	1	15	1
物品1	3	20	1
物品1	3	20	1
物品1	3	20	1
物品2	4	30	1
物品2	4	30	1

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

public void testMultiPack1(){
    // 版本一：改变物品数量为01背包格式
    List<Integer> weight = new ArrayList<>(Arrays.asList(1, 3, 4));
    List<Integer> value = new ArrayList<>(Arrays.asList(15, 20, 30));
    List<Integer> nums = new ArrayList<>(Arrays.asList(2, 3, 2));
    int bagWeight = 10;

    for (int i = 0; i < nums.size(); i++) {
        while (nums.get(i) > 1) { // 把物品展开为i
            weight.add(weight.get(i));
            value.add(value.get(i));
            nums.set(i, nums.get(i) - 1);
        }
    }

    int[] dp = new int[bagWeight + 1];
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight.get(i); j--) { // 遍历背包容量
            dp[j] = Math.max(dp[j], dp[j - weight.get(i)] + value.get(i));
        }
        System.out.println(Arrays.toString(dp));
    }
}

public void testMultiPack2(){
    // 版本二：改变遍历个数
    int[] weight = new int[] {1, 3, 4};
    int[] value = new int[] {15, 20, 30};
    int[] nums = new int[] {2, 3, 2};
    int bagWeight = 10;

    int[] dp = new int[bagWeight + 1];
    for(int i = 0; i < weight.length; i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            // 以上为01背包，然后加一个遍历个数
            for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
                dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
            System.out.println(Arrays.toString(dp));
        }
    }
}

分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。注意：每个数组中的元素不会超过100，数组的大小不会超过200

• 此题可以换一种表述：给定一个只包含正整数的非空数组nums，判断是否可以从数组中选出一些数字，使得这些数字的和等于整个数组的元素和的一半。
• 因此这个问题可以转换成01背包问题，传统的01背包要求选取的物品的重量之和不能超过背包的总容量，这道题则要求选取的数组的和恰好等于整个数组的元素和的一半。

1.确定dp数组以及下标的含义：dp[j]表示背包总容量是j，最大可以凑成j的子集总和为dp[j]。

2.确定递推公式：本题相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。所以递推公式：dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);

3.dp数组初始化：从dp[j]的定义来看，dp[0]一定是0.如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。**这样才能让dp数组在递推公式的过程中取得最大的价值，而不是被初始值覆盖了。**本题题目中只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。

4.遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

5.举例推导dp数组：dp[j]的数值一定是小于等于j的。如果dp[j]==j说明集合中的子集总和正好可以凑成总和j。如数组2 2 4 6 其dp[数组总和 / 2] != 数组总和 / 2。因此不能满足题意。

public boolean canPartition(int[] nums) {
        //01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2
    if(nums == null || nums.length == 0) return false;
    //求数组的总和
    int sum = 0;
    for(int i = 0; i < nums.length; i++) {
        sum += nums[i];
    }
    int target = sum / 2;
    //如果数组总和为奇数，则不可能分成两个元素和相等的子集
	if(sum % 2 == 1) return false;
    for(int i = 0; i < nums.length; i++) {
        for(int j = target; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i])
        }
    }
    return dp[target] == target;
}

最后一块石头的重量II

从一堆石头中，每次拿两块重量分别为x，y的石头，若x=y，则两块石头均粉碎；若x< y，两块石头变为一块重量为y-x的石头，求最后剩下的石头的最小重量（若没有剩下则返回0）

问题转化为：把一堆石头分成两堆，求两堆石头重量差的最小值。进一步分析：要让差值最小，两堆石头的重量都要接近sum/2，假设两堆分别为A,B，则A<sum/2,b>sum/2，若A更接近sum/2，B也相应更接近sum/2，则所得差值最小。

进一步转化：将一堆石头放进最大容量为sum/2的背包，求放进去的石头的最大重量MaxWeight，最终答案即为sum - 2*MaxWeight;

public int lastStoneWeightII(int[] stones) {
	int sum = 0;
    for(int i : stones) {
        sum += i;
    }
    int target = sum / 2;
    int[] dp = new int[target + 1];
    for(int i = 0; i < stones.length; i++) {
        for(int j = target; j >= stones[i]; j--) {
            dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
        }
    }
    return sum - 2 * dp[target];
}

目标和

每个数字都有两种状态：被进行“+”， 或者被进行“-”，因此可以将数组分成A和B两个部分：A部分的数字全部进行“+”操作，B部分的数字全部进行“-”操作。

设数组的和为sum，A部分的和为sumA，B部分的和为sumB。根据上面的分析可以得出sumA + sumB = sum（1）sumA - sumB = target（2）将1和2式相加可以得到2sumA = sum + target 即：sumA = (sum + target) / 2。自此原问题可以转化为01背包问题：有一些物品，第i个物品的重量为nums[i]，背包的容量为sumA，问：有多少种方式将背包恰好填满。

需要注意的是，由于每个数字都是非负整数，因此sumA,sumB,sum都是非负整数。根据(3)，2sumA一定为偶数（自然数的性质，2n是偶数），因此sum + target也应该是偶数。如果计算出的sum+target不是偶数，则与推导过程矛盾，本题无解。

1.确定dp数组以及下标的含义：dp[j]表示填满j这么大容量的背包，有dp[j]种方法。

2.确定递推公式：求装满背包有多少种方式，都是类似dp[j] += dp[j - nums[i]]。

3.dp数组初始化：从递推公式可以看出，在初始化dp[0]时一定要初始化为1，因为dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递推结果都是0。dp[0] = 1也可解释为装满容量为0的背包，有一种方法，就是装0件物品。dp[j]其他下标对于的数值应该初始化为0，从递推公式也可以看出，dp[j]要保证是0的初始值，才能正确的由dp[j - nums[i]]推导出来。

4.遍历顺序：nums放在外循环，target在内循环且内循环倒序。

5.举例推导dp数组：

输入：nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

ublic int findTargetSumWays(int[] nums, int target) {
	int sum = 0;
    for(int i : nums) {
        sum += i;
    }
    if(Math.abs(target) > sum) return 0;
    if((target + sum) % 2 == 1) return 0;
    int bagsize = (sum + target) / 2;
    int[] dp = new int[target + 1];
    
    for(int i = 0; i < nums.length; i++) {
        for(int j = bagsize; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[bagsize];
}

一和零

本题中strs数组里的元素就是物品，每个物品的数量都为1，而m和n相当于是一个背包，两个维度的背包。

1.dp数组的定义：dp[i] [j]表示最多有i个0和j个1的strs的最大子集的大小为dp[i] [j]

2.递推公式dp[i] [j] = Math.max(dp[i] [j],dp[i - zeroNum] [j - oneNum] + 1)，字符串的zeroNum和oneNum相当于物品的重量weight[i]，字符串本身的个数相当于物品的价值value[i]。

3.dp数组初始化：因为物品价值不会是负数，初始为0，保证递推的时候dp[i] [j]不会被初始值覆盖。

4.本题中物品就是strs里的字符串，背包容量就是题目描述中的m和n，遍历顺序还是01背包的遍历顺序。

5.举例推导dp数组：

public int findMaxForm(String[] strs, int m, int n) {
	int[][] dp = new int[m + 1][n + 1];
    for(String str : strs) {
        int zeroNum = 0;
        int oneNum = 0;
        for(char c : str.toCharArray()) {
            if(c == '0') zeroNum++;
            else oneNum++;
        }
        for(int i = m; i >= zeroNum; i--) {
            for(int j = n; j >= oneNum; j--) {
                dp[i][j] = Math.max(dp[i][j],dp[i - zeroNum][j - oneNum] + 1);
            }
        }
    }
    return dp[m][n];
}

零钱兑换II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

1.确定dp数组：dp[j]表示凑成总金额j的货币组合数。

2.确定递推公式：求装满背包有几种方法，一般公式都是dp[j] += dp[j - nums[i]];

3.dp[0]一定要为1，其是递推公式的基础。从dp[i]的含义上来讲就是，凑成总金额0的货币组合数为1。下标非0的dp[j]初始化为0，这样累加dp[j - coins[i]]的时候才不会影响真正的dp[j]。

4.确定遍历顺序：本题求的是组合数，所以外层for循环遍历物品，内存for遍历背包。

5.举例推导dp数组：

public int change(int amount, int[] coins) {
	int[] dp = int[amount + 1];
    dp[0] = 1;
    for(int i = 0; i < coins.length; i++) {
        for(int j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]]; 
        }
    }
    return dp[amount];
}

组合总和IV

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。注意：顺序不同的序列被视作不同的组合。

1.dp数组的定义：dp[j]表示凑成正整数为j的排列个数。

2.递推公式：dp[j] += dp[j - nums[j]];

3.dp数组的初始化：dp[0] = 1，非0下标初始化为0。

4.遍历顺序：本题求排列数，因此target(背包)放在外循环，将nums(物品)放在内循环，内循环从前到后遍历。

5.举例推导dp数组：

public int combinationSum4(int[] nums, int target) {
	int[] dp = new int[target + 1];
    dp[0] = 1;
    for(int j = 0; j <= target; j++) {
        for(int i = 0; i < nums.length; i++) {
            if(j - nums[i] >= 0) {
                dp[j] += dp[j - nums[i]];
            }
        }
    }
    return dp[target];
}

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

爬楼梯（进阶版）

假设你正在爬楼梯，需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？改为：一步一个台阶，两个台阶，三个台阶，......,直到m个台阶。问有多少种不同的方法可以爬到楼顶？

1.dp数组的定义：dp[i]表示爬到i个台阶的楼顶，有dp[i]种方法。

2.递推公式：dp[i] += dp[i - j];

3.dp数组初始化：dp[0] = 1，非0下标的dp[i]初始化为0，因为dp[i]是靠dp[i-j]累计上来的。

4.遍历顺序：本题是背包求排列数问题，所以需要target放在外循环，将nums放在内循环。

public int climbStairs(int n) {
	int[] dp = new int[n + 1];
    dp[0] = 1;
    for(int i = 1; i <= n; i++) {
        //此处的m表示最多可爬m个台阶
        for(int j = 1; j <= m; j++) {
            if(i - j >= 0) {
                dp[i] += dp[i - j];
            }
        }
    }
    return dp[n];
}

零钱兑换

给定不同面额的硬币coins和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。

1.dp数组的定义：dp[j]表示凑足总金额j所需钱币的最少个数。

2.确定递推公式：dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);

3.dp数组初始化：首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;由递推公式可知，非0下标必须初始化为一个最大的数，否则就会在选取最小值的过程中被初始值覆盖。

4.遍历顺序：本题求钱币最小个数，那么钱币有顺序和没有顺序都不影响钱币的最小个数。

5.举例推导dp数组：

public int coinChange(int[] coins, int amount) {
	int[] dp = new int[amount + 1];
    for(int i = 0; i < dp.length; i++) {
        dp[i] = Integer.MAX_VALUE;
    }
    dp[0] = 0;
    for(int i = 0; i < coins.length; i++) {
        for(int j = coins[i]; j <= amount; j++) {
            if(dp[j - coins[i]] != Integer.MAX_VALUE) {
                dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);
            }
        }
    }
    if(dp[amount] == Integer.MAX_VALUE) {
            return -1;
        }
    return dp[amount];
}

完全平方数

给定正整数n，找到若干个完全平方数，使得它们的和等于n。你需要让组成和的完全平方数的个数最少。

1.dp数组的定义：dp[j]表示和为j的完全平方数的最少数量。

2.确定递推公式：dp[j] = Math.min(dp[j - i*i] + 1,dp[j])

3.dp数组初始化：dp[0]表示和为0的完全平方数的最小数量，所以dp[0]=0。由递推公式可知，非0下标应初始为最大值。

4.遍历顺序：本题求的是个数与顺序无关，所以哪种遍历方式都可以。

5.举例推导dp数组：

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

打家劫舍系列

打家劫舍I

1.dp数组的定义：dp[i]表示考虑下标i（包括下标i）以内的房屋，最多可以偷窃的金额为dp[i]。

2.确定递推公式：决定dp[i]的因素就是第i房间偷还是不偷。如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i]，即第i - 1房一定是不考虑的，最多可以偷窃的金额为dp[i-2]加上第i房间偷到的钱。如果不偷第i房间，那么dp[i] = dp[i - 1]。然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i],dp[i - 1]);

3.dp数组初始化：从递推公式可以看出，递推公式的基础就是dp[0]和dp[1]，则dp[0]一定是nums[0]，dp[1]就是nums[0]和nums[1]的最大值，即 dp[1] = max(nums[0],nums[1]);

4.遍历顺序：dp[i]是根据dp[i-2]和dp[i - 1]推导出来的，那么一定是从前到后遍历。

5.举例推导dp数组：

public int rob(int[] nums) {
	if(nums == null && nums.length == 0) return 0;
    if(nums.length == 1) return nums[0];
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0],nums[1]);
    for(int i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]);
    }
    return dp[nums.length - 1];
}

打家劫舍II

对于一个数组成环的话主要有如下三种情况：

情况一：考虑不包含首尾元素

情况二：考虑包含首元素，不包含尾元素

情况三：考虑包含尾元素，不包含首元素

因为情况二和三都包含情况一，所以只需考虑情况二三就可以了。

public int rob(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        int result1 = robRange(nums,0,nums.length - 2);
        int result2 = robRange(nums,1,nums.length - 1);
        return Math.max(result1,result2);
    }

    public int robRange(int[] nums,int start,int end) {
        if(end == start) return nums[start];
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start],nums[start + 1]);
        for(int i = start + 2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]);
        }
        return dp[end];
    }

打家劫舍III

本题一定是要后序遍历，因为要通过递归函数的返回值来做下一步计算。

1.确定递归函数的参数和返回值

这里要求一个节点偷与不偷的两个状态所得到的的金钱，那么返回值就是一个长度为2的数组。参数为当前节点。返回数组就是dp数组且其定义为：下标为0记录不偷该节点所得到的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

2.确定终止条件：在遍历的过程中，如果遇到空节点的话，无论偷还是不偷都是0。相当于dp数组的初始化。

3.确定遍历顺序：首先明确的是使用后序遍历。通过递归左节点，得到左节点偷与不偷的金钱。通过递归右节点，得到右节点偷与不偷的金钱。

4.确定单层递归的逻辑：如果是偷当前节点，那么左右孩子就不能偷，val1 = cur.val + left[0] + right[0]；如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，val2 = max(left[0],left[1]) + max(right[0],right[1])；最后当前节点的状态就是{val2,val1}即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

5.举例推导dp数组

最后头结点就是取下标0和下标1的最大值就是偷得的最大金钱。

public int rob(TreeNode root) {
    int[] res = robAction1(root);
    return Math.max(res[0],res[1]);
}
public int[] robAction1(TreeNode root) {
	int[] dp = new int[2];
    if(root == null) return dp;
    
    int[] left = robAction1(root.left);
    int[] right = robAction1(root.right);
    
    dp[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
    dp[1] = root.val + left[0] + right[0];
    
    return dp;
}

股票系列

买卖股票的最佳时机I

主要约束条件就是在给出的股票数组中，最多只能交易一次，并计算出最大的利润。

1.dp数组的定义：dp[i] [0]表示第i天持有股票所得最多现金。dp[i] [1]表示第i天不持有股票所得最多现金。

2.递推公式：

如果第i天持有股票即dp[i] [0]，那么可以由两个状态推出来：

• 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1] [0]
• 第i天买入股票，所得现金就是买入今天的股票后所得的现金 即：-prices[i]

所以dp[i] [0]应该选所得现金最大的，则dp[i] [0] = max(dp[i - 1] [0],-prices[i]);

如果第i天不持有股票即dp[i] [1]，也可以由两个状态推出来：

• 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1] [1];
• 第i天卖出股票，所得现金就是今天股票价格卖出后所得现金减去买入时花费的现金 即：dp[i] [1] = prices[i] + dp[i -1] [0];

同样需要取两者的最大值。

3.dp数组初始化：由递推公式可知，do[0] [0]表示第0天持有股票，则其最大现金为-prices[0];dp[0] [1]表示第一天未持有股票的最大现金数为0。

4.遍历顺序：由递推公式可知是从前向后遍历的。

5.举例推导dp数组

本题中不持有股票状态所得金钱一定比持有股票状态得到的多！因此dp[5] [1]就是最终结果。

public int maxProfit(int[] prices) {
    if(prices == null || prices.length == 0) return 0;
    //dp[i][0]表示第i天持有股票的最大收益
    //dp[i][1]表示第i天不持有股票的最大收益
    int[][] dp = new int[prices.length][2];
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    for(int i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0],-prices[i]);
        dp[i][1] = Math.max(dp[i - 1][0] + prices[i],dp[i - 1][1]);
    }
    return dp[prices.length - 1][1];
}

买卖股票的最佳时机II

本题的主要约束是可以尽可能多次的进行交易，但是必须在再次购买之前出售掉之前的股票。

因为约束条件的改变，因为可以进行多次交易，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。那么第i天持有股票dp[i] [0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格 即：dp[i-1] [1] - prices[i]

public int maxProfit(int[] prices) {
    //动态规划
    int[][] dp = new int[prices.length][2];
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    for(int i = 1; i < prices.length; 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],dp[i - 1][0] + prices[i]);
    }
    return dp[prices.length - 1][1];
}

买卖股票的最佳时机III

本题的约束为最多可以完成两笔交易，并计算出所能获取的最大利润。

1.dp数组的定义：0：没有操作 1：第一次买入 2：第一次卖出 3：第二次买入 4.第二次卖出

dp[i] [j]中i表示第i天，j为[0 - 4]五个状态，dp[i] [j]表示第i天状态j所剩最大现金。

2.确定递推公式：

达到dp[i] [1]状态，有两个具体操作：选取其中的最大值

• 操作一：第i天买入股票了，那么dp[i] [1] = dp[i - 1] [0] - prices[i]
• 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i] [1] = dp[i - 1] [1]

同理dp[i] [2]也有两个操作：同样选取两者最大值

• 操作一：第i天卖出股票了，那么dp[i] [2] = dp[i - 1] [1] + prices[i]
• 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i] [2] = dp[i - 1] [2];

同理可推出剩下状态部分：

dp[i] [3]= max(dp[i - 1] [3], dp[i - 1] [2] - prices[i]);

dp[i] [4] = max(dp[i - 1] [4], dp[i - 1] [3] + prices[i]);

3.dp数组的初始化：在第0天时，只有买入的时候才需要初始化，即dp[0] [1] = -prices[0] 和 dp[0] [3] = -prices[0]

4.遍历顺序：从递推公式可以看出，需从前向后遍历。

5.举例推导dp数组：

两次卖出的状态现金最大一定是最后一次卖出。所以最终最大利润是dp[4] [4]

public int maxProfit(int[] prices) {
    if(prices.length == 0) return 0;
    //定义5种状态  0：没有操作  1.第一次买入  2.第一次卖出  3.第二次买入  4.第二次卖出
    int[][] dp = new int[prices.length][5];
    dp[0][1] = -prices[0];
    //初始化第二次买入的状态是确保最后结果是最多两次买卖的最大利润
    dp[0][3] = -prices[0];
    for(int i = 1; i < prices.length; i++) {
        dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
        dp[i][2] = Math.max(dp[i - 1][2],dp[i - 1][1] + prices[i]);
        dp[i][3] = Math.max(dp[i - 1][3],dp[i - 1][2] - prices[i]);
        dp[i][4] = Math.max(dp[i - 1][4],dp[i - 1][3] + prices[i]); 
    }
    return dp[prices.length - 1][4];
}

买卖股票的最佳时机IV

本题的约束条件为最多可以完成k笔交易，最多的交易次数由系统给出，计算所能获取的最大利润。可由III中的代码统计出规律

1.定义dp数组：题目要求至多有k笔交易，那么j的范围就定义为2*k+1。

2.确定递推公式：由之前的代码类比可知，当j为奇数时买入，偶数时卖出。

for (int j = 0; j < 2 * k - 1; j += 2) {
    dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
    dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}

3.dp数组的初始化：同理可推出dp[0] [j]，当j为奇数的时候都初始化为-prices[0]

for (int j = 1; j < 2 * k; j += 2) {
    dp[0][j] = -prices[0];
}

4.遍历顺序：同样为从前向后遍历。

5.举例推导dp数组：

最后一次卖出，一定是利润最大的，dp[prices.length - 1] [2 * k]

public int maxProfit(int k, int[] prices) {
    if(prices.length == 0) return 0;
    int[][] dp = new int[prices.length][2 * k + 1];
    for(int i = 1; i < 2 * k; i += 2) {
        dp[0][i] = -prices[0];
    }
    for(int i = 1;i < prices.length; i++) {
        for(int j = 0; j < 2 * k - 1; j += 2) {
            dp[i][j + 1] = Math.max(dp[i - 1][j + 1],dp[i - 1][j] - prices[i]);
            dp[i][j + 2] = Math.max(dp[i - 1][j + 2],dp[i - 1][j + 1] + prices[i]);
        }
    }
    return dp[prices.length - 1][2 * k];
}

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

本题的约束条件为可以尽可能地完成更多的交易，但是必须在再次购买之前出售掉之前的股票。卖出股票后，无法在第二天买入股票（即冷冻期为1天）

public int maxProfit(int[] prices) {
    if(prices == null || prices.length < 2) return 0;
    int[][] dp = new int[prices.length][4];
    dp[0][0] = -prices[0];
    for(int i = 1; i < prices.length; i++) {
        //0 —— 买入股票状态  操作一：前一天是持有股票状态  操作二：前一天是保持卖出股票状态或者前一天是冷冻期
        dp[i][0] = Math.max(dp[i - 1][0],Math.max(dp[i - 1][3],dp[i - 1][1]) - prices[i]);
        //1 —— 两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
        //操作一：前一天也是1状态  操作二：前一天是冷冻期
        dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][3]);
        //2 —— 今天卖出了股票  找到之前买入股票的状态  加上股票金额等于利润
        dp[i][2] = dp[i - 1][0] + prices[i];
        //3 —— 冷冻期的前一天一定是卖出股票状态
        dp[i][3] = dp[i - 1][2];
    }
    //应该选取后三种状态的最大值
    return Math.max(dp[prices.length - 1][3],Math.max(dp[prices.length - 1][1],dp[prices.length - 1][2]));
}

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

本题的约束条件为可以尽可能多地完成交易，但是每笔交易都需要支付手续费。如果已经购买了一支股票，在卖出它之前不能再继续购买股票。返回获得利润的最大值。

public int maxProfit(int[] prices, int fee) {
    //动态规划  买入时支付手续费
    int[][] dp = new int[prices.length][2];
    /*dp[0][0] = -prices[0] - fee;
        for(int i = 1; i < prices.length; 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]);
        }*/
    //也可卖出时才支付手续费
    dp[0][0] = -prices[0];
    for(int i = 1; i < prices.length; 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],dp[i -1][0] + prices[i] - fee);
    }
    return dp[prices.length - 1][1];
}

子序列、子数组系列

最长递增子序列

给你一个整数数组nums，找到其中最长严格递增子序列的长度。nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4

1.dp数组的定义：dp[i]表示i之前包括i的以nums[i]结尾的最长上升子序列的长度。

2.递推公式：位置i的最长上升子序列等于j从0到i-1各个位置的最长上升子序列+1的最大值。所以：if(nums[i] > nums[j]) dp[i] = max(dp[i],dp[j] + 1);

3.dp[i]的初始化：每一个i，对应的dp[i]起始大小至少都是1

4.遍历顺序：dp[i]是由0到i-1各个位置的最长升序子序列推导而来，那么遍历i一定是从前向后遍历。j其实就是0到i-1，遍历i的循环在外层，遍历j则在内层，代码如下：

for (int i = 1; i < nums.size(); i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
    }
    if (dp[i] > result) result = dp[i]; // 取最长的子序列
}

5.举例推导dp数组：

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

最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

1.dp数组的定义：dp[i]表示以下标i结尾的数组的连续递增的子序列长度。

2.确定递推公式：如果nums[i + 1] > nums[i]，那么以i+1为结尾的数组的连续递增子序列长度一定等于以i结尾的数组的连续递增的子序列长度+1。即：dp[i + 1] = dp[i] + 1;

3.dp数组的初始化：以下标i为结尾的数组的连续递增的子序列长度最少也应该是1，所以dp[i]初始为1。

4.从递推公式可知，dp[i + 1]依赖于dp[i]，所以一定是从前向后遍历的。

5.举例推导dp数组：

public int findLengthOfLCIS(int[] nums) {
    if(nums == null || nums.length== 0) return 0;
    if(nums.length == 1) return 1;
    int result = 0;
    int[] dp = new int[nums.length];
    for(int i = 0; i < nums.length; i++) {
        dp[i] = 1;
    }
    for(int i = 0; i < nums.length - 1; i++) {
        if(nums[i + 1] > nums[i]) {
            dp[i + 1] = dp[i] + 1;
        }
        if(dp[i + 1] > result) result = dp[i + 1];
    }
	return result;
}

最长重复子数组

给定两个整数数组A和B，返回两个数组中公共的、长度最长的子数组的长度。A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1]

1.dp数组的定义：dp[i] [j]表示以下标i - 1为结尾的A和以下标j - 1为结尾的B，最长重复子数组长度为dp[i] [j]

2.递推公式：根据dp[i] [j]的定义，dp[i] [j]的状态只能由dp[i - 1] [j - 1]推导出来。即当A[i - 1]和B[j - 1]相等的时候，dp[i] [j] = dp[i - 1] [j - 1] + 1;根据递推公式可知，遍历i和j要从1开始！

3.dp数组的初始化：根据dp[i] [j]定义可知，dp[i] [0]和dp[0] [j]都是没有意义的。但为了方便递推公式，所以dp[i] [0]和dp[0] [j]都初始化为0。假如A[0]和B[0]相同的话，dp[1] [1] = dp[0] [0] + 1，只有dp[0] [0]初始化为0，正好符合递推公式逐步累加起来。

4.遍历顺序：外层for循环遍历A，内存for循环遍历B。反过来也可以。同时题目是求长度最长的子数组的长度，所以再遍历的时候顺便把dp[i] [j]的最大值记录下来。

5.举例推导dp数组：

public int findLength(int[] nums1, int[] nums2) {
    //子序列可不连续  子数组须连续
    if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return 0;
    int result = 0;
    int[][] dp = new int[nums1.length + 1][nums2.length + 1];
    for(int i = 1; i <= nums1.length; i++) {
        for(int j = 1; j <= nums2.length; j++) {
            if(nums1[i - 1] == nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            if(dp[i][j] > result) result = dp[i][j];
        }
    }
    return result;
}

最长公共子序列

给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。若这两个字符串没有公共子序列，则返回0。text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。

1.dp数组的定义：dp[i] [j]表示长度为[0,i - 1]的字符串text1与长度为[0,j - 1]的字符串text2的最长公共子序列。

2.确定递推公式：如果text1[i - 1]与text2[j - 1]相同，那么找到了一个公共元素，所以dp[i] [j] = dp[i - 1] [j - 1] + 1;如果text1[i - 1]与text2[j - 1]不相同，则dp[i] [j] = max(dp[i - 1] [j],dp[i] [j - 1]);

3.dp数组的初始化：text1[0,i-1]和空串的最长公共子序列自然是0，所以dp[i] [0] = 0；同理dp[0] [j]也是0。其他下标都是随着递推公式逐步覆盖，初始为多少都可以，那么就统一初始为0。

4.遍历顺序：从递推公式可知，有三个方向可以推出dp[i] [j]，如图：

那么为了在递推的过程中，这三个方向都是经过计算的数值，所以要从前向后，从上到下遍历这个矩阵。

5.举例推导dp数组：

最后红框dp[text1.length()] [text2.length()]为最终结果。

public int longestCommonSubsequence(String text1, String text2) {
    if(text1 == null || text1.length() == 0 ||text2 == null || text2.length() == 0) return 0;
    int[][] dp = new int[text1.length() +1][text2.length() + 1];
    for(int i = 1; i <= text1.length(); i++) {
        char char1 = text1.charAt(i - 1);
        for(int j = 1; j <= text2.length(); j++) {
            char char2 = text2.charAt(j - 1);
            if(char1 == char2) {
                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[text1.length()][text2.length()];
}

最大子序和

给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

1.dp数组的定义：dp[i]：包括下标i之前的最大连续子序列和为dp[i]。

2.递推公式：dp[i - 1] + nums[i],即nums[i]加入当前连续子序列和。nums[i]，即从头开始计算当前连续子序列和。取最大值即可满足题意。

3.dp数组的初始化：从递推公式可以看出dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。根据dp数组的定义可知，dp[0]应初始化为nums[0]。

4.确定遍历顺序：由递推公式可知，需从前向后遍历

5.举例推导dp数组：

public int maxSubArray(int[] nums) {
	if(nums == null || nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int result = dp[0];
    for(int i = 1; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
        if(dp[i] > result) result = dp[i];
    }
    return result;
}

判断子序列

给定字符串s和t，判断s是否为t的子序列。

1.dp数组的定义：dp[i] [j]表示以下标i - 1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i] [j]。

2.递推公式：if(s[i - 1] == t[j - 1])，那么dp[i] [j] = dp[i - 1] [j - 1] + 1;因为找到了一个相同的字符，相同子序列长度自然要在dp[i - 1] [j - 1]的基础上加1

if(s[i - 1]) != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i] [j]的数值就是dp[i] [j - 1]。

3.dp数组的初始化：由递推公式可知，dp[0] [0]和dp[i] [0]要初始化为0。这里大家已经可以发现，在定义dp[i] [j]含义的时候为什么要以下标i - 1为结尾的字符串s，和以下标j - 1为结尾的字符串t，相同子序列的长度为dp[i] [j]。因为这样的定义在dp二维矩阵中可以留出初始化的区间，如图：

如果要是定义dp[i] [j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t，初始化时就会比较麻烦。dp[i] [0]表示以下标i-1为结尾的字符串，与空字符串的相同子序列长度，所以为0。dp[0] [j]同理。

4.遍历顺序：从递推公式可知遍历顺序应该是从上到下，从左到右的。

5.举例推导dp数组：

如果dp[s.length()] [t.length()]与字符串s的长度相同说明：s与t的最长相同子序列就是s，那么s就是t的子序列。

public boolean isSubsequence(String s, String t) {
	int[][] dp = new int[s.length() + 1][t.length() + 1];
    for(int i = 1; i <= s.length(); i++) {
        char char1 = s.charAt(i - 1);
        for(int j = 1; j <= t.length(); j++) {
            char char2 = t.charAt(j - 1);
            if(char1 == char2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }
    return dp[s.length()][t.length()] == s.length();
}

不同的子序列

给定一个字符串s和一个字符串t，计算在s的子序列中t出现的个数。

1.dp数组的定义：dp[i] [j]表示以i-1为结尾的s子序列中出现以j-1为结尾的t的个数。

2.递推公式：

当s[i - 1]与t[j - 1]相等时，dp[i] [j]可以有两部分组成。例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。所以当s[i - 1]与t[j - 1]相等时，dp[i] [j] = dp[i - 1] [j - 1] + dp[i - 1] [j]；当s[i - 1]与t[j - 1]不相等时，dp[i] [j]只有一部分组成，所以dp[i] [j] = dp[i - 1] [j]。

3.dp数组的初始化：由递推公式可知，dp[i] [0]和dp[0] [j]是一定要初始化的。dp[i] [0]表示以i - 1为结尾的s可以随便删除元素，出现空字符串的个数，那么dp[i] [0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。而dp[0] [j]表示空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。那么dp[0] [j]一定都是0，s无论如何也变不成t。dp[0] [0]应该是1，空字符串s可以删除0个元素变成空字符串t。

4.遍历顺序：从递推公式可知遍历顺序是从上到下，从左到右的，这样保证dp[i] [j]可以根据之前计算出来的数值进行计算。

5.举例推导dp数组：

public int numDistinct(String s, String t) {
    //dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t个数为dp[i][j]
    int[][] dp = new int[s.length() + 1][t.length() + 1];
    for(int i = 0; i <= s.length(); i++) {
        dp[i][0] = 1;
    }
    for(int i = 1; i <= s.length(); i++) {
        char char1 = s.charAt(i - 1);
        for(int j = 1; j <= t.length(); j++) {
            char char2 = t.charAt(j - 1);
            if(char1 == char2) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[s.length()][t.length()];
}

两个字符串的删除操作

给定两个单词word1和word2，找到使得word1和word2相同所需的最小步数，每步可以删除任意一个字符串中的一个字符

1.dp数组的定义：dp[i] [j]表示以i - 1结尾的字符串word1，和以j - 1结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。当word1[i - 1]与word2[j - 1]相同的时候，dp[i] [j] = dp[i - 1] [j - 1]；当word1[i - 1]与word2[j - 1]不相同的时候，有三种情况：

情况一：删word1[i - 1]，最少操作次数为dp[i - 1] [j] + 1

情况二：删word2[j - 1]，最少操作次数为dp[i] [j - 1] + 1

情况三：同时删除word1[i - 1]和word2[j - 1]，最少操作次数为dp[i - 1] [j - 1] + 2。取三种情况的最小值。

3.dp数组的初始化：从递推公式可以看出，dp[i] [0]和dp[0] [j]是一定要初始化的。且dp[i] [0]表示word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同，即可初始化为i。dp[0] [j]同理可初始化为j。

4.遍历顺序：从递推公式可知dp[i] [j]都是根据左上方、正上方、正左方推出来的。所以遍历的时候一定是从上到下、从左到右，这样保证dp[i] [j]可以根据之前计算出来的数值进行计算。

5.举例推导dp数组：

public int minDistance(String word1, String word2) {
    //dp[i][j]：以i-1为结尾的字符串word1，和以j-1为结尾的字符串word2，想要达到相等，所需要删除元素的最少次数
    int[][] dp = new int[word1.length() + 1][word2.length() + 1];
    for(int i = 0; i <= word1.length(); i++) {
        dp[i][0] = i;
    }
    for(int j = 0; j <= word2.length(); j++) {
        dp[0][j] = j;
    }
    for(int i = 1; i <= word1.length(); i++) {
        char char1 = word1.charAt(i - 1);
        for(int j = 1; j <= word2.length(); j++) {
            char char2 = word2.charAt(j - 1);
            if(char1 == char2) {
                dp[i][j] = dp[i - 1][j - 1];
            }else {
                dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,Math.min(dp[i - 1][j] + 1,dp[i][j - 1] + 1));
            }
        }
    }
    return dp[word1.length()][word2.length()];
}

编辑距离

给你两个单词word1和word2，请你计算出将word1转换成word2所使用的最少操作数。你可以对一个单词进行插入、删除、替换操作。输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

1.dp数组的定义：dp[i] [j]表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2的最少编辑次数。

2.递推公式：

在确定递推公式的时候，首先要考虑清楚编辑的几种操作，整理如下：

if (word1[i - 1] == word2[j - 1])
    不操作
if (word1[i - 1] != word2[j - 1])
    增
    删
    换

if(word1[i - 1] == word2[j - 1])那么说明不用任何编辑，dp[i] [j]就应该是dp[i - 1] [j - 1]。

if(word1[i - 1] != word2[j - 1])，此时就需要编辑了：

操作一：word1删除一个元素，那么就是以下标i-2为结尾的word1与j-1为结尾的word2的最近编辑距离再加上一个操作。即dp[i] [j] = dp[i - 1] [j] + 1。

操作二：word2删除一个元素，那么就是以下标i-1为结尾的word1与j-2为结尾的word2的最近编辑距离再加上一个操作。即dp[i] [j] = dp[i] [j - 1] + 1。

添加操作相当于变相的删除操作。word2添加一个元素，相当于word1删除一个元素，如图所示：

            a                         a     d
   +-----+-----+             +-----+-----+-----+
   |  0  |  1  |             |  0  |  1  |  2  |
   +-----+-----+   ===>      +-----+-----+-----+
 a |  1  |  0  |           a |  1  |  0  |  1  |
   +-----+-----+             +-----+-----+-----+
 d |  2  |  1  |
   +-----+-----+

操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1与j-2为结尾的word2的最近编辑距离加上一个替换元素的操作。即dp[i] [j] = dp[i - 1] [j - 1] + 1;取各种操作的最小值。

3.dp数组的初始化：dp[i] [0]表示以下标i-1为结尾的字符串word1和空字符串word2的最近编辑距离。

那么dp[i] [0]就应该是i，对word1里的元素全部做删除操作。同理dp[0] [j] = j;

4.遍历顺序：

所以在dp矩阵中一定是从左到右从上到下去遍历。

5.举例推导dp数组：

public int minDistance(String word1, String word2) {
    //dp[i][j]表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2的最少编辑次数
    int[][] dp = new int[word1.length() + 1][word2.length() + 1];
    for(int i = 0; i <= word1.length(); i++) dp[i][0] = i;
    for(int j = 0; j <= word2.length(); j++) dp[0][j] = j;
    for(int i = 1; i <= word1.length(); i++) {
        char char1 = word1.charAt(i - 1);
        for(int j = 1; j <= word2.length(); j++) {
            char char2 = word2.charAt(j - 1);
            if(char1 == char2) {
                dp[i][j] = dp[i - 1][j - 1];
            }else {
                dp[i][j] = Math.min(dp[i - 1][j - 1] + 1,Math.min(dp[i - 1][j] + 1,dp[i][j - 1] + 1));
            }
        }
    }
    return dp[word1.length()][word2.length()];
}

回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。输入："aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

1.dp数组的定义：布尔类型的dp[i] [j]表示区间范围[i,j]（注意是左闭右闭）的子串是否是回文子串，如果是回文子串dp[i] [j]为true，否则为false。

2.确定递推公式：当s[i]与s[j]不相等时，dp[i] [j]一定是false。当s[i]与s[j]相等时，分为三种情况：

情况一：下标i与j相同，同一个字符例如a，当然是回文子串

情况二：下标i与j相差为1，例如aa，也是回文子串

情况三：下标i与j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看到i到j区间是否是回文子串就看aba是否是回文子串就可以了，那么aba的区间就是i + 1与j - 1区间，这个区间是否是回文就看dp[i + 1] [j - 1]是否为true。递推公式如下：

if (s[i] == s[j]) {
    if (j - i <= 1) { // 情况一 和 情况二
        result++;
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        result++;
        dp[i][j] = true;
    }
}

result就是统计回文子串的数量。注意这里并没有列出当s[i] [j]不相等的时候，因为在dp[i] [j]初始化的时，就初始为了false。

3.dp数组的初始化：将dp[i] [j]全部初始化为false。

4.遍历顺序：首先从递推公式中可以看出，情况三是根据dp[i + 1] [j - 1]是否为true，才对dp[i] [j]进行赋值true的。dp[i + 1] [j - 1]在dp[i] [j]的左下角，如图：

如果矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1] [j - 1]，也就是根据不确定是不是回文的区间[i + 1,j - 1]来判断[i,j]是不是回文，那结果一定是不对的。所以一定要从下到上，从左到右遍历，这样保证dp[i+1] [j-1]都是经过计算的。

5.举例推导dp数组：

注意：因为dp[i] [j]的定义，所以j一定是大于等于i的，那么在填充dp[i] [j]的时候一定是只填充右上半部分。

public int countSubstrings(String s) {
	if(s == null || s.length() == 0) return 0;
    boolean[][] dp = new boolean[s.length()][s.length()];
    int result = 0;
    for(int i = s.length() - 1;i >= 0; i--) {
        char char1 = s.charAt(i);
        for(int j = i; j < s.length(); j++) {
            char char2 = s.charAt(j);
            if(char1 == char2 && (j - i <= 1 || dp[i + 1][j - 1])) {
                result++;
                dp[i][j] = true;
            }
        }
    }
    return result;
}

最长回文子序列

给定一个字符串s，找到其中最长的回文子序列，并返回该序列的长度。可以假设s的最大长度为1000。输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。

回文子串是需要连续的，回文子序列可以不是连续的。

1.dp数组的定义：字符串s在[i,j]范围内最长的回文子序列的长度为dp[i] [j]。

2.递推公式：如果s[i]与s[j]相同，那么dp[i] [j] = dp[i + 1] [j - 1] + 2；如图：

如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。加入s[i]的回文子序列长度为dp[i] [j - 1]。加入s[j]的回文子序列长度为dp[i - 1] [j]。取两者的最大值。

3.dp数组的初始化：首先考虑当i和j相同的情况，从递推公式可知其实计算不到i和j相同时候的情况。所以当i和j相同时，那么dp[i] [j] 一定是等于1的，即一个字符的回文子序列长度就是1。其它情况dp[i] [j]初始为0就行。

4.遍历顺序：

由递推公式可知，遍历i的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的。

5.举例推导dp数组：

红色框dp[0] [s.length() - 1]即为最终结果。

public int longestPalindromeSubseq(String s) {
	int[][] dp = int[s.length][s.length];
    for(int i = 0; i < s.length; i++) {
        dp[i][i] = 1;
    }
    for(int i = s.length() - 1; i >= 0; i--) {
        char char1 = s.charAt(i);
        for(int j = i + 1; j < s.length(); j++) {
            char char2 = s.charAt(j);
            if(char1 == char2) {
                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][s.length() - 1];
}

额外的题目

乘积最大子数组

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

考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能【负得更多】，即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。于是这里可以再为何一个min，它表示以第i个元素结尾的乘积最小子数组的乘积，即可得到以下动态规划转移方程：

max = Math.max(mx * nums[i],Math.max(nums[i],mn * nums[i]));
min = Math.min(mn * nums[i],Math.min(nums[i],mx * nums[i]));

public int maxProduct(int[] nums) {
    int max = nums[0],min = nums[0],result = nums[0];
    for(int i = 1; i < nums.length; i++) {
        int mx = max, mn = min;
        max = Math.max(mx * nums[i],Math.max(nums[i],mn * nums[i]));
        min = Math.min(mn * nums[i],Math.min(nums[i],mx * nums[i]));
        result = Math.max(result,max);
    }
    return result;
}

乘积为正数的最长子数组长度

positive[i]表示以下标i结尾的乘积为正数的最长子数组长度，negative[i]表示以下标i结尾的乘积为负数的最长子数组长度。

当i = 0时，以下标i结尾的子数组的长度为1，因此当nums[0] > 0时positive[0] = 1，当nums[0] < 0时，negative[0] = 1。

当i > 1时，根据nums[i]的值计算positive[i]和negative[i]的值。

• 当nums[i] > 0时，之前的乘积乘以nums[i]不会改变乘积的正负性。positive[i] = positive[i - 1] + 1。negative[i] = negative[i - 1] + 1|| 0，这时因为当negative[i - 1]=0时，negative[i]本身无法形成一个乘积为整数的子数组，所以要特殊判断。
• 当nums[i] < 0时，之前的乘积乘以nums[i]会改变乘积的正负性。positive[i] = negative[i - 1] + 1 || 0，这时因为当negative[i - 1] = 0时，positive[i]本身无法形成一个乘积为负数的子数组，所以要特殊判断。negative[i] = positive[i - 1] + 1。
• 当nums[i] = 0时，以下标i结尾的子数组的元素乘积一定为0，因此positive[i] = 0和negative[i] = 0。

public int getMaxLen(int[] nums) {
    int[] positive = new int[nums.length];
    int[] negative = new int[nums.length];
    if(nums[0] > 0) {
        positive[0] = 1;
    }else if(nums[0] < 0) {
        negative[0] = 1;
    }
    int maxLength = positive[0];
    for(int i = 1; i < nums.length; i++) {
        if(nums[i] > 0) {
            positive[i] = positive[i - 1] + 1;
            negative[i] = negative[i - 1] > 0 ? negative[i - 1] + 1 : 0;
        }else if(nums[i] < 0) {
            positive[i] = negative[i - 1] > 0 ? negative[i - 1] + 1 : 0;
            negative[i] = positive[i - 1] + 1;
        }else {
            positive[0] = 0;
            negative[0] = 0;
        }
        maxLength = Math.max(maxLength,positive[i]);
    }
    return maxLength;
}

翻转字符

如果一个由'0'和'1'组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是单调递增的。我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。返回使s单调递增的最小翻转次数。

输入：s = "010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。

输入：s = "00011000"
输出：2
解释：我们翻转得到 00000000。

由于字符串s的每个位置的字符可以是0或1，因此对于每个位置需要分别计算该位置的字符是0和该位置是1的情况下的最小翻转次数。用dp[i] [0]和dp[i] [1]分别表示下标i处的字符为0和1的情况下使得s[0,...i]单调递增的最小翻转次数。

当1<=i<=n时，考虑下标i处的字符。如果下标i处的字符是0，则只有当下标i-1处的字符是0时才符合单调递增；如果下标i处的字符是1，则下标i-1处的字符是0或1都符合单调递增，此时为了将翻转次数最小化，应分别考虑i-1处的字符是0和1的情况下需要的翻转次数，取两者的最小值。在计算dp[i] [0]和dp[i] [1]时，还需要根据s[i]的值决定下标i处的字符是否需要翻转。

public int minFlipsMonoIncr(String s) {
    //dp[i][0]表示前i个元素，最后一个元素为0的最小翻转次数
    //dp[i][1]表示前i个元素，最后一个元素为1的最小翻转次数
    int[][] dp = new int[s.length()][2];
    //初始化
    dp[0][0] = s.charAt(0) == '0' ? 0 : 1;
    dp[0][1] = s.charAt(0) == '1' ? 0 : 1;
    //状态转移
    for(int i = 1; i < s.length(); i++) {
        dp[i][0] = dp[i - 1][0] + (s.charAt(i) == '0' ? 0 : 1);
        dp[i][1] = Math.min(dp[i - 1][0],dp[i - 1][1]) + (s.charAt(i) == '1' ? 0 : 1);
    }
    return Math.min(dp[s.length() - 1][0],dp[s.length() - 1][1]);
}

最佳观光组合

给你一个正整数数组values，其中values[i]表示第i个观光景点的评分，并且两个景点i和j之间的距离为j-i。一对景点(i < j)组成的观光组合的得分为values[i] + values[j] + i - j，也就是景点评分之和减去它们之间的距离。返回一对观光景点能取得的最高分。

输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

可将递推公式拆分成values[i] + i 和values[j] - j两部分，这样对于统计景点j答案的时候，由于values[j] - j是固定不变的，因此最大化values[i] + i + values[j] - j的值其实就等价于求[0,j - 1]中values[i] + i的最大值mx，景点j的答案即为mx + values[j] - j。而mx的值我们只要从前往后遍历j的时候同时维护即可，这样每次遍历到景点j的时候，寻找使得得分最大的i就能从O(n)降至O(1)的时间复杂度，总时间复杂度就能从O(n^2)降至O(n)。

public int maxScoreSightseeingPair(int[] values) {
    //动态规划
    int dp = 0, result = 0;
    for(int i = 1; i < values.length; i++) {
        dp = Math.max(dp,values[i - 1] + i - 1);
        int j = i;
        result = Math.max(result,dp + values[j] - j);
    }
    return result;

丑数II

给你一个整数，请你找出并返回第n个丑数。丑数就是只包含质因数2、3或5的正整数。

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

public int nthUglyNumber(int n) {
    int[] dp = new int[n + 1];
    dp[1] = 1;
    int maxA = 1,maxB = 1,maxC = 1;
    for(int i = 2; i <= n ; i++) {
        int maxa = dp[maxA] * 2;
        int maxb = dp[maxB] * 3;
        int maxc = dp[maxC] * 5;
        dp[i] = Math.min(maxa,Math.min(maxb,maxc));
        if(maxa == dp[i]) maxA++;
        if(maxb == dp[i]) maxB++;
        if(maxc == dp[i]) maxC++;
    }
    return dp[n];
}

剪绳子

给你一根长度为n的绳子，请把绳子剪成整数长度的m段（m、n都是整数，n>1并且m>1），求出分成的每段绳子的最大乘积。例如，当绳子的长度是8时，把它剪成长度分别为2,3,3的三段，此时得到的最大乘积是18。

解决大问题的时候用到小问题的解并不是这三个数 真正的dp[1] = 0,dp[2] = 1,dp[3] = 2 但是当n=4时，4=2+2 2*2=4 而dp[2]=1是不对的 也就是说当n=1/2/3时，分割后反而比没分割的值要小，当大问题用到dp[j]时，说明已经分成了一个j一个i-j，这两部分又可以再分，但是再分部分比他本身没分割的要小，如果分了更小还不如不分。所以在这里指定大问题用到的dp[1],dp[2],dp[3]是他本身

public int cuttingRope(int n) {
	int[] dp = new int[n + 1];
    if(n <= 3) return n - 1;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    for(int i = 4; i <= n; i++) {
        for(int j = 1; j <= i / 2; j++) {
            dp[i] = Math.max(dp[i],dp[j] * d[i - j]);
        }
    }
    return dp[n];
}

机器人的运动范围

地上有一个m行n列的方格，从坐标[0,0]到坐标[m-1,n-1]。一个机器人从坐标[0,0]的格子开始移动它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

public int movingCount(int m, int n, int k) {
    //dp[i][j]表示是否能进入下标为i，j的方格中
    if(k == 0) return 1;
    boolean[][] dp = new boolean[m][n];
    dp[0][0] = true;
    int result = 1;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(i == 0 && j == 0 || get(i) + get(j) > k) continue;
            if(i - 1 >= 0) {
                dp[i][j] |= dp[i - 1][j];
            }
            if(j - 1 >= 0) {
                dp[i][j] |= dp[i][j - 1];
            }
            result += dp[i][j] ? 1 : 0;
        }
    }
    return result;
}
public int get(int x) {
    int res = 0;
    while(x != 0) {
        res += x % 10;
        x /= 10;
    }
    return res;
}

把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译成字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

动态规划解析：

• 状态定义：设动态规划列表dp，dp[i]代表以xi为结尾的数字的翻译方案数量。
• 转移方程：若xi和xi-1组成的两位数字可以被翻译，则dp[i] = dp[i - 1] + dp[i - 2]；否则dp[i] = dp[i - 1]。
  • 可被翻译的两位数区间：当xi-1 = 0时，组成的两位数是无法被翻译的（如01、02....），因此区间为[10,25]。
• 初始状态：dp[0] = dp[1] = 1，即无数字和第1位数字的翻译方法数量均为1
• 返回值：dp[n]，即数字的翻译方案数量。

public int translateNum(int num) {
    //dp[i]表示以下标i为结尾的数字的翻译方案数量
	String s = String.valueOf(num);
    int[] dp = new int[s.length() + 1];
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i <= s.length(); i++) {
        String temp = s.substring(i - 2,i);
        if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }else {
            dp[i] = dp[i - 1];
        }
    }
    return dp[s.length()];
}

n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第i个元素代表这n个骰子所能掷出的点数集合中第i小的那个的概率。

dp五步曲：假设投掷n个骰子总的投的次数为6^n。

1.状态定义：dp[i] [j]为投掷i个骰子点数和为j的次数。

2.状态转移：dp[i] [j]由dp[i - 1] [j - 1],dp[i - 1] [ j - 2],...,dp[i - 1] [j - 6]相加得到。举例：dp[2] [4] = dp[1] [3] + dp[1] [2] + dp[1] [1],dp[1] [0]=0，投1次点数和不可能为0

3.初始化：只需要初始化dp[1] [i] = 1即可。(1 <= i <= 6)

4.遍历顺序：显然dp[i]是需要dp[i-1]推导的，而dp[i] [j]是需要dp[i - 1] [j - k]推导的，因此j的遍历顺序没关系。

5.返回值：将这5*n+1种出现的次数/6^n就是答案。

public double[] dicesProbability(int n) {
    //dp[i][j]表示投掷完i枚骰子后，点数j出现的次数
    int[][] dp = new int[n + 1][6 * n + 1];
    for(int i = 1; i <= 6; i++) {
        dp[1][i] = 1;
    }
    for(int i = 2; i <= n; i++) {
        for(int j = i; j <= 6 * i; j++) {
            for(int cur = 1; cur <= 6; cur++) {
                if(j - cur <= 0) {
                    break;
                }
                dp[i][j] += dp[i - 1][j - cur];
            }
        }
    }
    double[] result = new double[n * 5 + 1];
    double m = Math.pow(6,n);
    for (int i = 0, t = n * 5; i <= t; ++i) {
        result[i] = dp[n][n + i] / m;
    }
    return result;
}

最长斐波那契数列

给定一个严格递增的正整数数组形成序列arr，找到arr中最长的斐波那契式的子序列的长度。如果一个都不存在，返回0。

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。

public int lenLongestFibSubseq(int[] arr) {
    int maxLength = 0;
    Map<Integer,Integer> maps = new HashMap<>();
    for(int i = 0; i < arr.length; i++) {
        maps.put(arr[i],i);
    }
    int result = 0;
    int[][] dp = new int[arr.length][arr.length];
    for(int i = 1; i < arr.length; i++) {
        for(int j = 0; j < i; j++) {
            int temp = arr[i] - arr[j];
            if(maps.containsKey(temp) && maps.get(temp) < j) {
                dp[i][j] = dp[j][maps.get(temp)] + 1;
                result = Math.max(result,dp[i][j]);
            }else {
                dp[i][j] = 2;
            }
        }
    }
    return result;
}

三角形中最小路径之和

给定一个三角形triangle，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层节点下标相同或者等于上一层节点下标+1的两个节点。如果正位于当前行的下标i，那么下一步可以移动到下一行的下标为i或i+1。

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）

在本题中，给定的三角形的行数为n，并且第i行包含了i+1个数。如果将每一行的左端对齐，那么会形成一个等腰直角三角形，如下所示：

[2]
[3,4]
[6,5,7]
[4,1,8,3]

动态规划

dp[i] [j]表示从三角形顶部走到位置(i,j)的最小路径和。位置(i,j)指的是三角形中第i行第j列的位置。（均从0开始编号）

由于每一步只能移动到下一行相邻的节点上，因此要想走到位置(i,j)，上一步就只能在位置(i-1,j-1)或者位置(i-1,j)。在这两个位置中选择一个路径和较小的来进行转移，状态转移方程为：dp[i] [j] = min(dp[i-1] [j-1],dp[i-1] [j]) + c[i] [j];其中c[i] [j]表示位置(i,j)对于的元素值。

注意第i行有i+1个元素，它们对于的j的范围为[0,i]。当j=0或j=i时，上述状态转移方程中有一些项是没有意义的。例如当j=0时，dp[i - 1] [j - 1]没有意义，因此状态转移方程为：dp[i] [0] = dp[i - 1] [0] + c[i] [0]。即当在第i行的最左侧时，只能从第i-1行的最左侧移动过来。当j=i时，dp[i-1] [j]没有意义，因此状态转移方程为：dp[i] [i] = dp[i - 1] [i - 1] + c[i] [i]。即在第i行的最右侧时，只能从第i-1行的最右侧移动过来。最终的答案即为dp[n-1] [0]到dp[n - 1] [n - 1]中的最小值。

边界条件可以定义为dp[0] [0] = c[0] [0]。即在三角形的顶部时，最小路径和就等于对应位置的元素值。

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

矩阵中的距离

给定一个由0和1组成的矩阵mat，请输出一个大小相同的矩阵，其中每一个格子是mat中对应位置元素到最近的0的距离。两个相邻元素间的距离为1。

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

public int[][] updateMatrix(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    // 初始化动态规划的数组，所有的距离值都设置为一个很大的数
    int[][] dist = new int[m][n];
    for (int i = 0; i < m; ++i) {
        Arrays.fill(dist[i], Integer.MAX_VALUE / 2);
    }
    // 如果 (i, j) 的元素为 0，那么距离为 0
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 0) {
                dist[i][j] = 0;
            }
        }
    }
    // 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i - 1 >= 0) {
                dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
            }
            if (j - 1 >= 0) {
                dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
            }
        }
    }
    // 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
    for (int i = m - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            if (i + 1 < m) {
                dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
            }
            if (j + 1 < n) {
                dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
            }
        }
    }
    return dist;
}

单词拆分

给出一个字符串s和一个字符串列表wordDict作为字典。请你判断是否可以利用字典中出现的单词拼接出s。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

定义dp[i]表示字符串前i个字符组成的字符串s[0..i-1]是否能被空格拆分成若干个字典中出现的单词。从前往后计算考虑转移方程，每次转移的时候需要枚举包含位置i-1的最后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可。

则需要枚举s[o..i-1]中的分割点j，看s[0..j-1]组成的字符串s1（默认j=0时s1为空串）和s[j..i-1]组成的字符串s2是否都合法，如果两个字符串均合法，那么按照定义s1和s2拼接成的字符串也同样合法。由于计算dp[i]时已经计算出了dp[0..i-1]的值，因此字符串s1是否合法可以直接由dp[j]得知，剩下的只需要看s2是否合法即可。对于边界条件，定义dp[0]=true表示空串合法。

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

接雨水

给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

对于下标i，下雨后水能到达的最大高度等于下标i两边的最大高度的最小值，下标i处能接的雨水量等于下标i处的水能到达的最大高度减去height[i]。

创建两个长度为n的数组leftMax和rightMax。对于0<=i<=n，leftMax[i]表示下标i及其左边的位置中height的最大高度，rightMax[i]表示下标i及其右边的位置中height的最大高度。

显然，leftMax[0] = height[0]，rightMax[n-1] = height[n-1]。两个数组的其余元素的计算如下：

• 当1 <= i <= n - 1时，leftMax[i] = max(leftMax[i - 1],height[i])
• 当0 <= i <= n - 2时，rightMax[i] = max(rightMax[i - 1],height[i])

因此可以正向遍历数组height得到数组leftMax的每个元素值，反向遍历数组height得到数组rightMax的每个元素值。在得到数组leftMax和rightMax的每个元素值之后，对于0<=i<n，下标i处能接的雨水量等于min(leftMax[i],rightMax[i]) - height[i]。遍历每个下标位置即可得到能接的雨水总量。

public int trap(int[] height) {
    //动态规划
    if(height.length <= 2) return 0;
    int[] maxLeft = new int[height.length];
    int[] maxRight = new int[height.length];

    //记录每个柱子左边柱子最大高度
    maxLeft[0] = height[0];
    for(int i = 1; i < height.length; i++) {
        maxLeft[i] = Math.max(maxLeft[i - 1],height[i]);
    }
    //记录每个柱子右边柱子最大高度
    maxRight[height.length - 1] = height[height.length - 1];
    for(int j = height.length - 2; j >=0; j--) {
        maxRight[j] = Math.max(maxRight[j + 1],height[j]);
    }

    //求和
    int result = 0;
    for(int i = 0; i < height.length; i++) {
        int h = Math.min(maxLeft[i],maxRight[i]) - height[i];
        if(h > 0) result += h;
    }
    return result;
}

解码方法

一条包含字母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" 在映射中并不等价。

public int numDecodings(String s) {
    int[] dp = new int[s.length() + 1];
    dp[0] = 1;
    for(int i = 1; i <= s.length(); i++) {
        if(s.charAt(i - 1) != '0') {
            dp[i] += dp[i - 1];
        }
        if(i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[s.length()];
}

不同的二叉搜索树

给定一个整数n，求以1...n为节点组成的二叉搜索树有多少种？

解题思路：

dp[3]就是元素1为头结点搜索树的数量+元素2为头结点搜索树的数量+元素3为头结点搜索树的数量。

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树的数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

1.dp数组的定义：dp[i]表示1到i为节点组成的二叉搜索树的个数。

2.递推公式：dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] j相当于是头结点的元素，从1遍历到i为止。所以递推公式：dp[i] += dp[j - 1] * dp[i - j]；j-1为以j为头结点左子树节点数量，i-j为以j为头结点右子树节点数量。

3.dp数组的初始化：dp[0] = 1; 即空节点也是一棵二叉搜索树。

4.遍历顺序：由递推公式可知，遍历顺序是从前向后的。

public int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    for(int i = 1; i<= n; i++) {
        for(int j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp[n];
}

最长定差子序列

给你一个整数数组arr和一个整数difference，请你找出并返回arr中最长等差子序列的长度，该子序列中相邻元素之间的差等于difference。子序列是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从arr派生出来的序列。

输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。

从左往右遍历arr，并计算出以arr[i]为结尾的最长的等差子序列的长度，取所有长度的最大值，即为答案。

令dp[i]表示以arr[i]为结尾的最长的等差序列的长度，我们可以在arr[i]左侧找到满足arr[j] = arr[i] - d的元素，将arr[i]加到以arr[j]为结尾的最长的等差序列的末尾，这样可以递推地从dp[j]计算出dp[i]。

由于总是在左侧找一个最近的等于arr[i] - d元素并取其对应dp值，因此直接用dp[v]表示以v为结尾的最长的等差子序列的长度，这样dp[v-d]就是要找的左侧元素对应的最长的等差子序列的长度，因此转移方程为dp[v] = dp[v - d] + 1。

public int longestSubsequence(int[] arr, int difference) {
    int ans = 0;
    Map<Integer, Integer> dp = new HashMap<Integer, Integer>();
    for (int v : arr) {
        dp.put(v, dp.getOrDefault(v - difference, 0) + 1);
        ans = Math.max(ans, dp.get(v));
    }
    return ans;
}

最大正方形

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

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

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

dp[i,j]表示以(i,j)为右下角，且只包含1的正方形的边长最大值。如果能计算出所有dp(i,j)的值，那么其中的最大值即为矩阵中只包含1的正方形的边长最大值，其平方即为最大正方形的面积。

对于每个位置(i,j)，检查在矩阵中该位置的值：

• 如果该位置的值是0，则dp(i,j) = 0，因为当前位置不可能在由1组成的正方形中；
• 如果该位置的值是1，则dp(i,j)的值由其上方、左方和左上方的三个相邻位置的dp值决定，即当前位置的元素值等于三个相邻位置的元素中的最小值加1，状态转移方程如下：

dp[i] [j] = Math.min(dp[i - 1] [j - 1],Math.min(dp[i - 1] [j],dp[i] [j - 1])) + 1;此外还需要考虑边界条件。如果i和j中至少有一个为0，则以位置(i,j)为右下角的最大正方形的边长和只能是1，因此dp(i,j) = 1

public int maximalSquare(char[][] matrix) {
    int maxSide = 0;
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return maxSide;
    }
    int rows = matrix.length, columns = matrix[0].length;
    int[][] dp = new int[rows][columns];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            if (matrix[i][j] == '1') {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }
    int maxSquare = maxSide * maxSide;
    return maxSquare;
}