hot150-19-动态规划系列

holic-x...大约 16 分钟

难度说明：🟢简单🟡中等🔴困难

hot150-19-动态规划系列

一维动态规划（part 01）

🟢01-爬楼梯（70）

1.题目内容

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

2.题解思路

👻方法1：动态规划（`dp[i]=dp[i-1]+dp[i-2]`）

思路分析：穷举分析规律：f(n) = f(n-1) + f(n-2)，【爬N阶的方案个数】为【爬N-1阶的方案个数】+【爬N-2阶的方案个数】

可以先通过穷举方法理解思路的演变，例如从n=0开始，依次分析爬n阶需要多少种方法：

n=0：1种（0）
n=1：1种（1）
n=2：2种（1+1、0+2）
n=3：3种（1+2 1+1+1、0+2+1）
n=4：5种（1+1+2、0+2+2 1+2+1、1+1+1+1、0+2+1+1）
结合规律分析：当要爬第n阶的时候，它的方法相当于是基于第n-1阶的方案再爬1阶 + 基于第n-2的方案再爬2阶，即等价于爬N阶的方案个数实际等于爬N-1+爬N-2的方案个数，基于此可以看到这种思路很像斐波那契数列的调调，可以基于动态规划思路实现（将问题拆分为多个子问题）

/**
 * 070 爬楼梯
 */
public class Solution1 {
    public int climbStairs(int n) {
        // 1.dp 数组定义(dp[i]表示爬i阶的方案个数)
        int[] dp = new int[n+1];
        // 2.初始化dp
        dp[0] = 1; // 爬0阶有1种方案
        dp[1] = 1; // 爬1阶有1种方案
        // 3.构建dp
        for(int i=2;i<=n;i++){
            // 公式：爬N阶的方案=爬N-1的方案+爬N-2的方案
            dp[i] = dp[i-1] + dp[i-2];
        }
        // 4.返回所求答案
        return dp[n];
    }
}

复杂度分析
- 时间复杂度：O（n）
- 空间复杂度：O（n）需构建dp数组存储每一阶的方案

👻方法2：动态规划（空间优化版）

思路分析：基于【方法1】中动态规划思路，题中要求第N的方案，观察动态规划公式，n 阶方案只与其前两阶有关，因此可以考虑通过构建滚动数组的方式，每次滚动记录前两阶的方案数，进而达到空间优化的效果

/**
 * 070 爬楼梯
 */
public class Solution2 {
    // 动态规划（空间优化版本）
    public int climbStairs(int n) {
        // 1.定义滚动数组要素
        int p = 1; // 前N-2阶
        int q = 1; // 前N-1阶
        int r = 0; // N阶方案计数

        // 需对临界条件进行额外处理
        if(n==0 || n== 1){
            return 1;
        }

        // 2.根据公式计算第N阶的方案数，并滚动记录
        for(int i=2;i<=n;i++){
            // 公式：爬N阶的方案=爬N-1的方案+爬N-2的方案
            r = p + q;
            // 滚动记录
            p = q;
            q = r;
        }
        // 3.返回结果
        return r;
    }
}

复杂度分析
- 时间复杂度：O（n）
- 空间复杂度：O（1）对比【方案1】此处优化了空间占用，只使用了常数级别的空间

🟡02-打家劫舍（198）

1.题目内容

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

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

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

2.题解思路

👻方法1：动态规划

思路分析：先分析偷窃规律，然后分析出其规律方程（n表示多少间房屋，从n=1开始分析）
- n=1：只有一间房屋，则偷这一间即为最高
- n=2：有两间房屋，由于相邻两间不能连着偷，因此只能偷其中一间，选择价值较高的来偷（max{nums[0],nums[1]}）
- n=K：当n>2，则此时偷窃有两种思路（对于每一个房间都可以选择偷或者不偷）
  - 如果偷窃第K间房屋，则不能偷窃第K-1间房屋，偷窃总金额=max（前K-2间房屋金额）+第K间房屋金额
  - 如果不偷第K间房屋，则偷窃总金额=max（前K-1间房屋金额）
- 基于上述分析，则可得到相应的方程式：dp[k]=max{dp[k-2]+nums[k],dp[k-1]}，也就是说最终偷窃的总金额是由这两种场景构成的
- 说明：代码实现上可以先把大致框架定下来（动态规划的设计），然后在调试的过程中去完善边界条件

/**
 * 198 打家劫舍
 */
public class Solution1 {
    // 动态规划思路
    public int rob(int[] nums) {
        // 边界条件判断
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }

        // 1.dp[]定义：dp[i]表示经过i个房子后可劫取的最大值
        int[] dp = new int[len];
        // 2.初始化dp
        dp[0] = nums[0]; // 第1间房屋：只有一种选择（偷）
        dp[1] = Math.max(nums[0], nums[1]); // 第2间房屋：有两种方案（不能连着偷，只能选最大的来偷）
        /**
         * 3.构建dp（n>2的情况下）：对于第i间房屋的选择有两种情况：
         * - 偷：如果偷则不能连着偷，此时偷窃金额为dp[i-2] + nums[i]
         * - 不偷：如果不偷则跳过这个房屋，此时偷窃金额为dp[i-1](表示其带着上一轮偷来的前跳过这间房屋)
         * - 而对于方案的选择则需从这两个方案中计算得到 max ，选择偷窃金额最大的方案
         */
        for (int i = 2; i < len; i++) {
            // 分别计算两种方案
            int doIt = dp[i - 2] + nums[i]; // 偷，不能连着偷
            int undo = dp[i - 1]; // 不偷
            dp[i] = Math.max(doIt, undo); // 选择偷窃金额最高的方案
        }

        // 返回偷窃的最大金额
        return dp[len - 1]; // 偷窃金额是累加的，所以此处所有房屋都逛遍了，返回dp最后一个值即可
    }
}

复杂度分析
- 时间复杂度：O（n）n为房屋总数
空间复杂度：O（n）需构建dp数组维护每间房的偷窃方案的偷窃金额的最大值

👻方法2：动态规划（空间优化版本）

思路分析：同【方案1】中的动态规划思路类似，此处从状态转移方程分析来看：dp[k]=max{dp[k-2]+nums[k],dp[k-1]}，第N间房的偷窃方案之和前两个房间的偷窃的最大金额有关，因此此处可以参考【爬楼梯】的动态规划空间优化思路，基于滚动数组的方式来优化空间

/**
 * 198 打家劫舍
 */
public class Solution2 {
    // 动态规划思路（空间优化版本）
    public int rob(int[] nums) {
        // 临界条件判断
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0]; // 只有一间，偷
        }
        if (len == 2) {
            return Math.max(nums[0], nums[1]); // 只有两间，选择最大价值的偷
        }

        // n>2的情况，dp[i] = max{dp[i-2]+nums[i],dp[i-1]} 不能连着偷
        int p = nums[0]; // 表示dp[i-2] 初始化为nums[0]（第1间偷得最大值）
        int q = Math.max(nums[0], nums[1]); // 表示dp[i-1] 初始化为 Math.max(nums[0],nums[1]);（第2间偷得最大值）
        int r = 0; // 表示dp[i] 第i间房屋偷得的最大值
        int max = Integer.MIN_VALUE;
        for (int i = 2; i < len; i++) {
            // 确定偷窃方案
            int doIt = p + nums[i];
            int undo = q;
            r = Math.max(doIt, undo);
            max = Math.max(max, r); // 每次确定方案偷完之后更新一下max

            // 滚动记录
            p = q;
            q = r;
        }
        // 返回结果
        return max;
    }
}

复杂度分析
- 时间复杂度：O（n） n 为房屋间数
- 空间复杂度：O（1）基于滚动数组的空间优化，此处只需要用到常数级别的空间占用

🟡03-单词拆分（139）

1.题目内容

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

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

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

2.题解思路

👻方法1：动态规划

思路分析：核心：如果dp[k]可以被拆分，则dp[j]也可以被拆分，且从j+1到K的位置也能被拆分
- （1）定义dp数组（dp[i]表示从(0,i)的位置字符串可以被拆分）
- （2）初始化dp（dp[0]为true，其他默认初始化为false（此处dp[0]没有含义））
- （3）状态转移方程确定
  - 如果说如果dp[i]可以被拆分，则(0,j)、(j,i)也能够被拆分，据此得到状态转移方程为：dp[i] = dp[j] && check(j,i)
- （4）构建dp
  - 根据状态转移方程构建dp数组，最终返回dp[len]（表示(0,len)位置的字符串是否可被拆分）
- （5）验证dp

/**
 * 139 单词拆分
 */
public class Solution1 {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 1.dp[i]定义 表示(0,i)位置的字符串可以被拆分
        boolean[] dp = new boolean[s.length() + 1];
        // 2.初始化数组（dp[0]设为true（不具备含义） 其他默认设为false）
        Arrays.fill(dp, false);
        dp[0] = true;
        // 3.状态转移方程分析：如果(0,i)可被拆分，则中间引入一个点(0,j)(j,i)也能够被拆分
        // 4.初始化dp
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                // 构建dp元素
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        // 返回结果
        return dp[s.length()];
    }
}

复杂度分析
- 时间复杂度：O（n²）n 为字符串长度，每次遍历一个位置，要枚举n个分割点，找到满足的分割点
- 空间复杂度：O（n）需构建dp数组

🟡04-零钱兑换（322）

1.题目内容

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

2.题解思路

👻方法1：动态规划

思路分析：
- （1）dp 定义：dp[i]表示凑成i金额所需硬币的最少个数
- （2）dp 初始化：dp[0]初始化为0，其他数据用MAX填充
- （3）状态转移方程：对于金额i，如果要使用最少硬币凑成i，那么最理想的方案是dp[i-coins[j]] + 1（即 dp【当前要凑的金额减去某个硬币值】+ 1 ）
  - 同理这个dp[i-coins[j]]的方案是有很多的，因此需要遍历coins数组来选择一个最理想的方案，进而得到状态转移方程：dp[i] = min{ dp[i], dp[i-coin[j]]+1 }
- （4）双层遍历：外层背包，内层物品
  - 外层循环：确定i位置（遍历每个i位置封装dp）
  - 内存循环：通过状态转移方程计算dp[i]（遍历每个硬币，得到最优的方案）

/**
 * 322 零钱兑换
 */
public class Solution1 {
    /**
     * 动态规划：背包问题（外层背包，内层物品）
     * 用最少的硬币个数凑零钱
     */
    public int coinChange(int[] coins, int amount) {
        // 1.dp 定义：dp[i] 表示凑够i零钱需要的最少硬币数
        int[] dp = new int[amount + 1];

        // 2.初始化dp(求min,此处除了dp[0]，其他元素可以设为MAX,或者一个无业务影响的数值（例如amount+1）)
        Arrays.fill(dp, amount + 1); // Integer.MAX_VALUE
        dp[0] = 0;
        /**
         * 3.状态转移方程
         * dp[i] 如何获得，其最理想的状态就是减去一个任意硬币金额，然后数量+1 即可得到最优解，但这个硬币的方案选择有很多种，因此要择选min
         * 即 dp[i] = min{ dp[i] , dp[i-coins[j]] + 1}
         * 只要保证dp[i-count[j]]也是最少硬币数即可获得最优解
         */
        // 4.构建dp 寻找最优解
        for (int i = 1; i <= amount; i++) { // 外层循环确定i位置，用于构建dp[i]
            for (int j = 0; j < coins.length; j++) { // 内层循环寻找最优解（找到最理想的dp[i]）
                // 此处需限定条件coins[j]<i 否则数组越界异常
                if (i - coins[j] >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        // 返回结果
        return dp[amount] > amount ? -1 : dp[amount]; // 区分是否可以凑的情况
    }
}

复杂度分析
- 时间复杂度：O（m*n）m 表示 amount，n表示硬币种类（物品数量）
- 空间复杂度：O（n）构建dp数组存储元素

🟡05-最长递增子序列（300）

1.题目内容

给你一个整数数组 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 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

2.题解思路

👻方法1：动态规划

思路分析
- （1）dp定义：dp[i]表示以当前i位置元素结尾连续子序列的最大值长度
- （2）dp初始化：初始化为1（每个元素本身就是一个独立的升序序列）
- （3）状态转移方程：如何确定i位置的最大连续子序列，既然i位置是作为结尾，则需要考虑两点：dp[i] = max{dp[i],dp[j]+1}
  - 必须接在(0,i-1)之间某个比它（nums[i]）小的数后面才能构成升序序列
  - 比它小的数所在位置假设为j，则j可能会有很多(j1、j2.....)，因此要选择以某个j位置结尾能够构成最长连续序列的，只有接在这个数后面才能构成最长升序序列
- （4）构建dp：双层循环
  - 外层循环：确定i位置
  - 内层循环：检索(0,i)之间的比nums[i]小且该切割点位置可以构成最长连续序列（即可能会有很多dp[i]组合，要选择能够构成最长的连续序列的）

/**
 * 300 最长递增子序列
 */
public class Solution1 {
    // 最长递增子序列
    public int lengthOfLIS(int[] nums) {
        // 1.dp定义：dp[i] 表示以i位置结尾的最长连续升序序列的长度
        int[] dp = new int[nums.length];
        // 2.初始化（全初始化为1，每个数组元素本身可以作为一个独立的升序序列）
        Arrays.fill(dp, 1);
        /**
         * 3.状态方程
         * dp[i]如何获取：
         * 1.升序：从(0,i)的位置nums[i]小的元素，拼在其后面才能构成升序序列
         * 2.最长：步骤1中获取到的切割点j可能会有很多个，因此在这些可拼接的切割点中选择一个以其结尾构成最长连续序列的进行拼接，即dp[j]最大，拼在其后面才能构成最长
         */
        // 4.构建dp
        // 外层循环：确定i位置
        for (int i = 0; i < nums.length; i++) {
            // 内层循环：确定(0,i)之间可以可nums[i]构成最长连续子序列的点
            for (int j = 0; j < i; j++) {
                // nums[j]<nums[i] 才能构成升序
                if (nums[j] < nums[i]) {
                    // 更新max（满足升序条件前提下，不断更新max）
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        // 遍历dp数组，找到最长的连续序列
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            max = Math.max(max, dp[i]);
        }
        return max == Integer.MIN_VALUE ? -1 : max;
    }
}

hot150-19-动态规划系列

预览: