动态规划

动态规划是把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常用于解决有重叠子问题和最优子结构性质的问题。

🔍解题步骤：确定状态、设计状态转移方程、考虑初始条件和边界情况、计算顺序、优化代码。

在使用动态规划解题时，我们需要思考：

❓ 什么是“已知态”？

❓ 什么是“未知态”？

❓ 通过“已知态”如何去获取“未知态”？

✅解题步骤一：确定状态。

🔖 动态规划其实就是通过“❗已知态”去获取“❓未知态”的状态转移算法。通过一个“📝备忘录”去记录“状态”，在下次需要的时候不需要重新计算，可以直接使用。

👉 确定状态一般三个步骤：

  1. 研究最优策略的最后一步，一般是列举最后一步的所有可能进行分析。
  2. 通过研究最后一步与倒数第二步或第三步…之间的关系发现规律，化为子问题。在这个过程中，我们需要确定“已知态”和“未知态”。
  3. 根据子问题来创建状态数组保存“已知态”。一般来说，子问题有几个变量就是几维数组。

❗ 最关键的地方就是要确定状态数组的每个元素表示什么。状态数组通常是 dp[i] 或 dp[i][j]。

✅解题步骤二：设计状态转移方程。

🔖 动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。状态转移方程就是用来表示它们的公式。换言之就是设计出一个递推公式。

❗ 设计状态转移方程就是思考“如何通过 已知态 去获取 未知态 ？”，并将它们的关系用公式表示出来。这也是动态规划中最关键的一步。

✅解题步骤三：初始条件和边界情况。

🔖 初始条件：用状态转移方程无法计算出来，但我们又需要它的定义。即给出递推公式的基本条件。

🔖 边界情况：根据题目和状态转移方程判断边界情况，剔除出界情况。

✅解题步骤四：计算顺序。

❗ 通过思考“要想计算本次状态还需要依靠哪些状态”来确定计算顺序。换句话说，就是确定计算顺序要利用之前得出的结果来判断。一般是从小到大，从上到下，从左到右。

✅解题步骤五：优化代码。

🔖 动态规划可以说是一种“空间换时间”的算法。所以对于优化动态规划代码。我们可以选择：

👉 优化空间：减少状态转移变量的记录数。例如，那些只需要使用一次的转移状态变量，可以在使用后，通过覆盖的方式让其去记录新的状态转移变量。这样就可以减少内存消耗。

👉 优化时间：减少状态转移的时间。例如，用更好的算法去减少计算递推式的时间。

❗ 在使用动态规划解题时，应该先解题再优化，把解题放在第一位。



例题训练

爬楼梯

🔍题目要求

难度：简单 | LeetCode | 🔗链接直达

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

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

📃示例 1：

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

📃示例 2：

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

🎗️提示：

  • 1 <= n <= 45

💡题目分析

1️⃣ 在该题目中，最后一步是走到第 n 阶。那么它的上一步可能是第 n - 1 阶也可能是第 n - 2 阶。因为我们可以走一步或者走两步。

  • 假设为第 n - 1 阶，那么能到达第 n 阶的方法只有一种，即“走一步”。
  • 假设为第 n - 2 阶，那么能到达第 n 阶的方法有两种，即“一步一步走”或“一次走两步”。

那么继续对倒数第二步（第 n - 1 阶 或第 n - 2 阶）分析，我们也能得出类似的结果。那么我们就能够推断出第 n 阶只与第 n - 1 阶和第 n - 2 阶有关。

要想知道走到第 n 阶有多少种不同的方法，那么首先就要知道走到第 n - 1 阶和第 n - 2 阶有多少不同的方法。“未知态”就是走到第 n 阶有多少种不同的方法；“已知态”就是走到第 n - 1 阶和第 n - 2 阶有种多少不同的方法。那么就可以得出状态数组 dp[i] 表示走到第 i 阶有多少种不同的方法。

2️⃣ 通过“状态数组 dp[i] 表示走到第 i 阶有多少种不同的方法”和“要想知道走到第 i 阶有多少种不同的方法，那么首先就要知道走到第 i - 1 阶和第 i - 2 阶有多少不同的方法。”，我们能够得出状态转移方程为：dp[i] = dp[i - 1] + dp[i - 2]。

3️⃣ 初始条件为 dp[1] 和 dp[2]，因为我们无法用之前的状态得出它们的值。那么边界条件也显而易见了，为 i >= 3。

4️⃣ 由于需要根据 f(i - 1) 和 f(i - 2) 得出 f(i)，那么计算顺序就是 f(1) -> f(n)。

⌨️代码实现

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

♻️代码优化

从上述代码中可以看到，它利用到的状态只有 dp[i - 2] 和 dp[i - 1]，那么就可以简化为两个变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int dp1 = 1;
        int dp2 = 2;
        int tmp = 0;
        for (int i = 3; i <= n; i++) {
            tmp = dp2;
            dp2 = dp1 + dp2;
            dp1 = tmp; 
        }
        return dp2;
    }
}

最长回文子串

🔍题目要求

难度：中等 | LeetCode | 🔗链接直达

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

📃示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

📃示例 2：

1
2
输入：s = "cbbd"
输出："bb"

🎗️提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

💡题目分析

1️⃣ 最优决策下的最后一步是“最长回文子串的第一个字符的下标为 i，最后一个字符下标为 j。这里用 f(i, j) 表示下标从 i 到 j 为最长回文子串（包含 i 和 j）。依此类推，倒数第二步就是 f(i + 1, j - 1)，倒数第三步就是 f(i + 2, j - 2)…

从中我们可以看出，要想 f(i, j) 成立，就必须满足“f(i + 1, j - 1) 成立”和“s[i] == s[j]”。s[i] 表示字符串的第 i 个字符。

那么就能得出“已知态”就是 f(i + 1, j - 1)，“未知态”就是 f(i, j)。使用状态数组 dp[i][j] 来保存“已知态”。dp[i][j] 表示下标从 i 到 j 的字符子串，如果是回文子串则为 true。因为我们假定 f(i, j) 表示 i 到 j 为最长回文子串是最优策略。所以在非最优策略的时候，f(i, j) 表示的应该是下标从 i 到 j 的字符子串，并不一定是回文子串。

2️⃣ 根据“状态数组 dp[i][j]”和“要想 dp[i][j] 成立，就必须满足 dp[i + 1][j - 1] == true 和 s[i] == s[j]。”可以得出状态转移方程为：dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]。

3️⃣ 对于初始条件和边界情况的判断，需要先列一个 dp表格，这里假设字符串长度为 7，如下表：

0 1 2 3 4 5 6
✔️ end
❌ ✔️
❌ ❌ ✔️
❌ ❌ ❌ ✔️
❌ ❌ ❌ ❌ ✔️
❌ ❌ ❌ ❌ ❌ ✔️
❌ ❌ ❌ ❌ ❌ ❌ ✔️start

上述表格中，❌表示错误情况，不需要考虑；✔️表示我们需要计算的 true，✖️表示我们需要计算的 false；start 和 end 分别表示开始遍历的起点和终点。

💡那么可以得出以下几种情况：

  1. i > j：错误情况，下标不可能存在 i > j 的情况，这样子串就变成逆序了，故排除。
  2. i = j：即只有一个字符时，永远为回文子串，所以 dp[i][j] 为 true。
  3. i < j：使用状态转移方程 dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j] 进行判断。
    • s[i] != s[j]：必为 false。
    • s[i] == s[j] && i + 1 == j：即两个字符，且两个字符相等时，永远为回文子串，所以 dp[i][j] 为 true。
    • s[i] == s[j] && i + 1 < j： dp[i][j] = dp[i + 1][j - 1]。

边界条件：0 <= i <= j < s.length()。

💡假设要求 dp[0][6] 那么就要先求 dp[1][5]，还要先求 dp[2][3]。那么我们就知道，要求表格上面的值时，应该先求表格下面的值。

初始条件：i = s.length() - 1、j = i。

4️⃣ 根据上面的分析和表格，我们可以得出计算顺序是“从下到上”、“从左到右”。

⌨️代码实现

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
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        boolean[][] dp = new boolean[len][len];
        /** 回文子串的字符数量（最长回文子串长度） */
        int maxLen = 1;
        /** 回文子串的开始下标 */
        int start = 0;
        
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (i == j) {
                    dp[i][j] = true;
                } else if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    dp[i][j] = i + 1 == j ? s.charAt(i) == s.charAt(j) : dp[i + 1][j - 1];
                }
                
				    // 如果当前子串是回文子串且长度比最长回文子串的长度长，则更新下标。
                if (dp[i][j] && (j - i + 1) >= maxLen) {
                    start = i;
                    maxLen = j - i + 1;
                }
            }
        }

        // 如果无回文子串，则返回第一个字符
        return s.substring(start, start + maxLen);
    }
}

♻️代码优化

暂时想不到应该如何优化…

1
<优化代码>

最长递增子序列

🔍题目要求

难度：中等 | LeetCode | 🔗链接直达

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

📃示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

📃示例 2：

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

📃示例 3：

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

🎗️提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

🆙进阶：

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

💡题目分析

1️⃣ 最优策略下的最后一步：下标为 i 的元素是最长严格递增子序列的最后一个数，长度为 n。这里用 f(i) = n 来表示。那么倒数第二步则为 f(j) = n - 1，倒数第三步则为 f(k) = n - 2 …

在这些最优决策的步骤下，包含以下关系：

  1. i > j > k。
  2. f(k) + 2 = f(j) + 1 = f(i) + 1。

那么，要想得到 f(i) 的值，就要先求 f(j) 的值。

所以，可以看出“已知态”就是 f(j)，“未知态”就是 f(i)。状态数组 dp[i] 用来表示以下标 i 结尾的最长严格递增子序列的长度。

2️⃣ 从上述中，我们总结出几点：

  • j < i：j 与 i 不一定是相邻的，但是它们一定是连续的。
  • nums[j] < nums[i]：i 所指向的数一定是大于 j 所指向的数，因为是递增子序列。
  • dp[i]：意味着在以下标 i 结束的递增子序列中，长度最长。

那么，状态转移方程：在满足 nums[j] < nums[i]（递增）的情况下，dp[i] = max{dp[0], ..., dp[i - 1]} + 1。

3️⃣ 通过上述状态转移方程可以得知，我们需要一个循环 i 用来遍历 nums数组，另一个循环 j 用来往回遍历 dp数组。那么初始条件：dp[0] = 1、i = 1、j = i - 1；边界条件: nums.length > i > j >= 0。

4️⃣ 计算顺序：i 从左到右遍历 nums数组，j 从右到左比较 dp数组。

⌨️代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len == 1) return 1;
        int[] dp = new int[len];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < len; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (dp[j] == 0) {
                    dp[j] = 1;
                }
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            // 获取最长严格递增子序列的长度
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

♻️代码优化

暂时想不到应该如何优化…

1
<优化代码>

<题目>

🔍题目要求

难度：简单 | 中等 | 困难 | <来源> | 🔗链接直达

<题目要求>

📃示例：

1
<示例>

🎗️提示：

  • <提示>

💡题目分析

<具体的题目分析>1️⃣2️⃣3️⃣4️⃣

⌨️代码实现

1
<代码实现>

♻️代码优化

<优化描述>

1
<优化代码>


📌最后：希望本文能够给您提供帮助，文章中有不懂或不正确的地方，请在下方评论区💬留言！

🔗参考文献：

▶️ bilibili - 【动态规划专题班】ACM总冠军、清华+斯坦福大神带你入门动态规划算法；侯卫东. –九章算法