【LeetCode Hot100 动态规划】

动态规划五部曲

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

简单动态规划问题

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

dp数组含义
dp[i]：爬 i 层楼梯有 dp[i] 种方法

递推公式
爬到第 i 层，由于每次只能爬 1 或 2 个台阶，那么上一步可能在第 i-1 层或者第 i - 2 层。爬到第 i-1 层有 dp[i-1] 种方法，爬到第 i-2 层有 dp[i-2] 种方法，所以得到递推公式：
dp[i] = dp[i-1] + dp[i-2];

初始化
dp[0] = 1;
dp[1] = 1;

遍历顺序
因为得到 dp[i] 需要知道 dp[i-1] 和 dp[i-2]，所以是正序遍历。

代码

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

dp数组含义
dp[i] 考虑下标 i (包含), 偷的最大的金币数量。

递推公式
在 i 的位置，考虑：
偷 i ：dp[i-2] + nums[i] // i - 1 不能偷，所以是 dp[i-2] 然后加上第 i 个
不偷 i ：dp[i-1] // 考虑i-1，但是不代表 i-1 一定被偷
综上，得到递推公式：
dp[i] = max(dp[i-2] + nums[i], dp[i-1])

初始化
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1])

遍历顺序
正序

代码

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

01背包类问题

01背包基础

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

二维动态数组

dp数组含义
i 来表示物品、j表示背包容量。
dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。

递推公式
不放物品 i：背包容量为 j，里面不放物品 i 的最大价值是 dp[i - 1][j]。
放物品 i：背包空出物品 i 的容量后，背包容量为 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] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

遍历顺序
先遍历物品或者先遍历背包都可以。

一维动态数组

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

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

初始化
全都初始化为0

遍历顺序
遍历顺序：先遍历物品，后遍历背包，遍历背包要倒序遍历（因为是01背包问题，每一个物品只能选择一次）

分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

dp数组含义
在本题中，所有元素和为sum，那么能在数组中找到元素和为 sum/2 的数字，就返回true。
将该问题抽象为01背包，每一个数字的重量和价值都是数字的数值。sum/2 就是背包的容量和价值，dp[sum/2] = sum/2 背包就装满了，即找到了元素和为 sum/2 的数字。
01背包中，dp[j] 表示： 容量（所能装的重量）为 j 的背包，所背的物品价值最大可以为 dp[j]。
如果背包所载重量为target， dp[target]就是装满 背包之后的总价值，因为 本题中每一个元素的数值既是重量，也是价值，所以，当 dp[target] = target 的时候，背包就装满了。

递推公式
这里是使用一维dp动态数组
dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])

初始化
初始化为0

遍历顺序
遍历顺序：先遍历物品，后遍历背包，遍历背包要倒序遍历（因为是01背包问题，每一个物品只能选择一次）

代码

class Solution {
    // 所有元素和为sum，那么能在数组中找到元素和为 sum/2 的数字，就返回true
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        //总和为奇数，不能平分
        if(sum % 2 != 0) return false;
        int[] dp = new int[sum / 2 + 1];
        for(int i = 0; i < nums.length; i++) {
            for(int j = sum / 2; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if (dp[sum / 2] == sum / 2) {
            return true;
        }
        return false;
    }
}

完全背包类问题

完全背包基础

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

dp数组含义
把该问题抽象为完全背包问题
dp[j] 装满容量为j的背包，最少物品数为 dp[j]
即凑够总金额为 j 时，最少的硬币个数为 dp[j]

递推公式
选第 i 个时：dp[j-coins[i]] + 1
不选第 i 个时：dp[j]
dp[j] = min(dp[j-coins[i]] + 1, dp[j])

初始化
dp[0] = 0，
由于状态方程取min，所以非零下标初始化为INT_Max

遍历顺序
因为是求最小硬币个数，所以先遍历物品或者背包都可以;
因为是完全背包，物品可以选无数次，所以 j 是正序遍历

代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE); 
        dp[0] = 0;  // 初始化0
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
                if (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];
    }
}

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

dp数组含义
把该问题抽象为完全背包问题
dp[j] 装满容量为j的背包，最少物品数为 dp[j]
即凑够整数 n 时，最少需要的完全平方数个数为 dp[j]

递推公式
选第 i 个时：dp[j - i * i] + 1
不选第 i 个时：dp[j]
dp[j] = min(dp[j-coins[i]] + 1, dp[j])

初始化
dp[0] = 0，
由于状态方程取min，所以非零下标初始化为INT_Max

遍历顺序
因为是求最少完全平方数的个数，所以先遍历物品或者背包都可以;
因为是完全背包，物品可以选无数次，所以 j 是正序遍历

代码

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 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];
    }
}

零钱兑换II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。

dp数组含义
把该问题抽象为完全背包问题
dp[j] 装满容量为j的背包，有 dp[j] 种装法
即凑够总金额，共有 dp[j] 种凑法。

递推公式
dp[j] += dp[ j - coins[i] ]

初始化
dp[0] = 1

遍历顺序
求的是组合，因此要先遍历物品后遍历背包；
因为是完全背包问题，所以背包是正序遍历。

代码

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

组合总和IV

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

dp数组含义
把该问题抽象为完全背包问题
dp[j] 装满容量为j的背包，有 dp[j] 种装法
即凑够目标整数 target，共有 dp[j] 种凑法。

递推公式
dp[j] += dp[ j - coins[i] ]

初始化
dp[0] = 1

遍历顺序
求的是排列（不同排列顺序视为不同的组合），因此要先遍历背包后遍历物品；
因为是完全背包问题，所以背包是正序遍历。

代码

class Solution {
    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]) {
                    // 排列问题的话需要判断容量
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }
}

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

dp数组含义
单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词，说明就是一个完全背包！

dp[i] : 字符串长度为 i 的话，dp[i] 为true，表示可以拆分为一个或多个在字典中出现的单词。

递推公式
如果确定 dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
所以递推公式是 if ( [j, i] 这个区间的子串出现在字典里 && dp[j] 是true ) 那么 dp[i] = true。

初始化
dp[0] = true ；
非零下标初始化为 false;

遍历顺序
本题需要强调物品之间的顺序：
拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。
“apple”, “pen” 是物品，那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。
因此是求排列，那么就要先遍历背包再遍历物品。

代码

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] bp = new boolean[s.length() + 1];
        bp[0] = true;
        // 先遍历背包容量
        for(int i = 1; i <= s.length(); i++) {
            // 后遍历物品；!bp[i] 作用是剪枝
            for (int j = 0; j < i && !bp[i]; j++) {
                if (set.contains(s.substring(j, i)) && bp[j]) {
                    bp[i] = true;
                }
            }
        }
        return bp[s.length()];
    }
}

子序列问题

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

dp数组含义
dp[i] 表示 i 之前包括i 的以 nums[i] 结尾的最长递增子序列的长度

递推公式
位置 i 的最长升序子序列等于 j 从 0 到 i-1 各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。

初始化
全部初始化为 1

代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int result = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                // 内循环寻找 从 0 到 i - 1 各个位置的最长升序子序列
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

乘积最大子数组