3164 个字词
16 分钟
动态规划
首次发布: 2025-04-09
... 次访问
Course Notes
Algorithms

动态规划#

动态规划其实就是动态的调整策略，来达到最优解。它的核心思想是将复杂问题分解成简单子问题，通过保存子问题的解来避免重复计算。动态规划通常适用于具有重叠子问题和最优子结构性质的问题。

动态规划问题可以大致分为以下几类：

  1. 线性DP：问题状态是一维的，通常依赖于前一个或前几个状态。
  2. 背包问题：在一系列物品中进行选择，以在满足某些约束（如总重量或体积）的同时最大化（或最小化）总价值。
  3. 区间DP：状态由一个区间 [i, j] 定义，通常通过合并子区间的最优解来求解。
  4. 序列DP：在序列上进行操作，如最长子序列、子数组等问题。
  5. 状态压缩DP：当状态的维度过多但每一维的取值范围很小时，可以用一个整数的二进制位来表示状态。

下面将通过一系列经典例题来具体阐述。

基础线性DP#

线性DP是最基础的动态规划类型，其状态通常定义在一个一维数组上，dp[i] 的值依赖于 dp[i-1], dp[i-2] 等。

Example Problem Leetcode 70. 爬楼梯

原理： 假设 dp[i] 是爬到第 i 级台阶的方法数。要到达第 i 级，可以从第 i-1 级爬一步上来，也可以从第 i-2 级爬两步上来。因此，状态转移方程为 dp[i] = dp[i-1] + dp[i-2]，这本质上是一个斐波那契数列。

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2, current;
        for (int i = 3; i <= n; ++i) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
};

Example Problem Leetcode 198. 打家劫舍

原理： 不能抢劫相邻的房子。定义 dp[i] 为抢劫到第 i 家房子时能获得的最大金额。对于第 i 家，我们有两个选择：

  1. 不抢第 i 家：最大金额等于抢到第 i-1 家的最大金额，即 dp[i-1]。
  2. 抢第 i 家：那么就不能抢第 i-1 家，最大金额为 nums[i] + dp[i-2]。 状态转移方程为 dp[i] = max(dp[i-1], nums[i] + dp[i-2])。
#include <vector>
#include <algorithm>

class Solution {
public:
    int rob(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        if (n == 1) return nums[0];
        
        int prev2 = 0, prev1 = 0;
        for (int i = 0; i < n; ++i) {
            int current = std::max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
};

背包问题#

背包问题是组合优化的经典问题，核心是在给定容量的背包和一组物品中，如何选择物品以达到价值最大化。

Example Problem Leetcode 322. 零钱兑换 (完全背包)

原理： 给定不同面额的硬币和总金额，计算凑成总金额所需的最少硬币数量。这是典型的“完全背包”问题，每种硬币可以无限次使用。 定义 dp[i] 为凑成金额 i 所需的最少硬币数。对于金额 i，它可以由 dp[i - coin] 加上一枚 coin 硬币得到。 状态转移方程为 dp[i] = min(dp[i], dp[i - coin] + 1)，其中 coin 是可用的硬币面额。

#include <vector>
#include <algorithm>

class Solution {
public:
    int coinChange(std::vector<int>& coins, int amount) {
        std::vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = std::min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

Example Problem Leetcode 416. 分割等和子集 (0/1背包)

原理： 判断一个数组是否可以被分割成两个和相等的子集。这个问题可以转化为：能否从数组中找到一个子集，其和等于数组总和的一半。这是一个“0/1背包”问题。 背包容量为 target = sum / 2，物品为数组中的每个数字。定义 dp[j] 为是否能凑成和为 j。 状态转移方程为 dp[j] = dp[j] || dp[j - num]。为避免重复使用同一个元素，内层循环需要从后向前遍历。

#include <vector>
#include <numeric>

class Solution {
public:
    bool canPartition(std::vector<int>& nums) {
        int sum = std::accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        
        std::vector<bool> dp(target + 1, false);
        dp[0] = true;
        
        for (int num : nums) {
            for (int j = target; j >= num; --j) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }
};

序列DP#

序列DP处理与序列或字符串相关的问题，如最长子序列、子数组、编辑距离等。

Example Problem Leetcode 300. 最长递增子序列

原理： 寻找一个序列中最长的递增子序列的长度。定义 dp[i] 为以 nums[i] 结尾的最长递增子序列的长度。为了计算 dp[i]，我们需要遍历 j 从 0 到 i-1，如果 nums[i] > nums[j]，则 dp[i] 可以从 dp[j] 转移而来，即 dp[i] = max(dp[i], dp[j] + 1)。

#include <vector>
#include <algorithm>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        std::vector<int> dp(nums.size(), 1);
        int maxLen = 1;
        for (size_t i = 1; i < nums.size(); ++i) {
            for (size_t j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = std::max(dp[i], dp[j] + 1);
                }
            }
            maxLen = std::max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

Example Problem Leetcode 139. 单词拆分

原理： 判断一个字符串是否可以被字典中的单词拼接而成。定义 dp[i] 为字符串 s 的前 i 个字符（s[0...i-1]）是否可以被拆分。dp[i] 为 true 的条件是：存在一个 j < i，使得 dp[j] 为 true，并且子串 s[j...i-1] 在字典中。 状态转移方程为 dp[i] = dp[j] && check(s.substr(j, i-j))。

#include <string>
#include <vector>
#include <unordered_set>

class Solution {
public:
    bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
        std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
        int n = s.length();
        std::vector<bool> dp(n + 1, false);
        dp[0] = true;

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && dict.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

Example Problem Leetcode 152. 乘积最大子数组

原理： 由于存在负数，最大乘积可能由两个负数相乘得到。因此，在每个位置 i，我们需要同时记录以 nums[i] 结尾的“最大乘积”和“最小乘积”（可能为负）。 max_dp[i] = max(nums[i], max(max_dp[i-1] * nums[i], min_dp[i-1] * nums[i])) min_dp[i] = min(nums[i], min(max_dp[i-1] * nums[i], min_dp[i-1] * nums[i])) 最终结果是所有 max_dp[i] 中的最大值。

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxProduct(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        int maxProd = nums[0];
        int currentMax = nums[0];
        int currentMin = nums[0];

        for (size_t i = 1; i < nums.size(); ++i) {
            int tempMax = currentMax;
            currentMax = std::max({nums[i], currentMax * nums[i], currentMin * nums[i]});
            currentMin = std::min({nums[i], tempMax * nums[i], currentMin * nums[i]});
            maxProd = std::max(maxProd, currentMax);
        }
        return maxProd;
    }
};

Example Problem Leetcode 32. 最长有效括号

原理： 寻找最长的有效（格式正确）括号子串的长度。定义 dp[i] 为以 s[i-1] 结尾的最长有效括号子串的长度。

  • 如果 s[i-1] 是 (，dp[i] 必为 0。
  • 如果 s[i-1] 是 )，我们需要找到与之匹配的 (。
    • 如果 s[i-2] 是 (，则 dp[i] = dp[i-2] + 2。
    • 如果 s[i-2] 是 )，并且在 s[i - dp[i-1] - 2] 的位置是 (，则 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]。
#include <string>
#include <vector>
#include <algorithm>

class Solution {
public:
    int longestValidParentheses(std::string s) {
        int n = s.length();
        if (n < 2) return 0;
        std::vector<int> dp(n, 0);
        int maxLen = 0;

        for (int i = 1; i < n; ++i) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0);
                }
                maxLen = std::max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }
};

Example Problem Leetcode 1027. 最长等差数列

原理： 寻找数组中最长的等差数列的长度。由于需要公差信息，一维DP不足以表示状态。定义 dp[i][diff] 为以 nums[i] 结尾、公差为 diff 的等差数列的长度。 状态转移：遍历 j 从 0 到 i-1，计算公差 diff = nums[i] - nums[j]，则 dp[i][diff] = dp[j][diff] + 1。 由于 diff 可能为负，我们可以给它一个偏移量来作为数组索引。

#include <vector>
#include <unordered_map>

class Solution {
public:
    int longestArithSeqLength(std::vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) return n;
        
        std::vector<std::unordered_map<int, int>> dp(n);
        int maxLength = 0;
        
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int diff = nums[i] - nums[j];
                int length = 2;
                if (dp[j].count(diff)) {
                    length = dp[j][diff] + 1;
                }
                dp[i][diff] = length;
                maxLength = std::max(maxLength, length);
            }
        }
        return maxLength;
    }
};

Example Problem Leetcode 72. 编辑距离

原理： 计算将一个单词转换成另一个单词所需的最少操作（插入、删除、替换）次数。定义 dp[i][j] 为 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作数。

  • 如果 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]。
  • 否则，我们可以进行三种操作：
    • 替换：dp[i-1][j-1] + 1
    • 删除（word1）：dp[i-1][j] + 1
    • 插入（到 word1）：dp[i][j-1] + 1 取三者中的最小值。
#include <string>
#include <vector>
#include <algorithm>

class Solution {
public:
    int minDistance(std::string word1, std::string word2) {
        int m = word1.length();
        int n = word2.length();
        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));

        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = std::min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                }
            }
        }
        return dp[m][n];
    }
};

区间DP#

区间DP的状态通常定义在一个区间 [i, j] 上，最终目标是求解整个区间的答案。

Example Problem Min-Cut

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：

给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。你可以按顺序完成切割，也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。

返回切棍子的 最小总成本 。

Solution:

  • 切割成本特点：每次切割的成本等于当前要切割木棍的长度
  • 可调整顺序：可以按任意顺序进行切割，目标是最小化总成本
  • 子问题重叠：不同切割顺序会导致相同区间的重复计算

状态定义为 dp[i][j]， 表示从切点 cuts[i] 到切点 cuts[j] 之间的最小切割成本。注意，需要添加 0 和 n 作为边界，它们不是真正的切点。

状态转移方程为

dp[i][j]=min⁡k=i+1j−1(dp[i][k]+dp[k][j])+(cuts[j]−cuts[i])dp[i][j] = \min_{k=i+1}^{j-1} (dp[i][k] + dp[k][j]) + (cuts[j] - cuts[i])

讲白了就是我们要实现从 i 到 j 的最小切割成本，首先我们要选择一个切点 k 在 (i, j) 之间进行切割，将木棍 (cuts[i], cuts[j]) 分成两段。总成本等于切割这两段的成本之和，再加上当前这次切割的成本 cuts[j] - cuts[i]。

为什么要先排序 ?

排序是为了确保切点按顺序排列，便于定义和计算区间。 添加 0 和 n 是为了表示木棍的两端，方便处理边界情况。

from typing import List

def minCost(n: int, cuts: List[int]) -> int:
    cuts.sort()     # 排序是为了方便计算切割成本
    cuts = [0] + cuts + [n] # 在开头和结尾添加0和n，表示棍子的两端
    m = len(cuts)
    
    # dp[i][j] 表示从 cuts[i] 到 cuts[j] 的最小切割成本
    dp = [[0] * m for _ in range(m)]
    
    # 枚举区间长度
    for length in range(2, m):
        # 枚举区间左端点
        for i in range(m - length):
            j = i + length
            dp[i][j] = float('inf')
            # 枚举区间内的切割点 k
            for k in range(i + 1, j):
                cost = dp[i][k] + dp[k][j] + cuts[j] - cuts[i]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][m - 1]

DP与其他技巧#

Example Problem Leetcode 42. 接雨水

原理： 虽然此题有更优的双指针解法，但也可以用动态规划求解。对于每个位置 i，它能接的雨水量取决于其左右两侧最高的柱子中的较小者，即 min(left_max[i], right_max[i]) - height[i]。 我们可以用两个DP数组 left_max 和 right_max 分别预处理每个位置左侧和右侧的最高柱子高度。

  • left_max[i] = max(left_max[i-1], height[i])
  • right_max[i] 从右向左计算：right_max[i] = max(right_max[i+1], height[i])
#include <vector>
#include <algorithm>

class Solution {
public:
    int trap(std::vector<int>& height) {
        int n = height.size();
        if (n == 0) return 0;
        
        std::vector<int> left_max(n);
        left_max[0] = height[0];
        for (int i = 1; i < n; ++i) {
            left_max[i] = std::max(left_max[i - 1], height[i]);
        }
        
        std::vector<int> right_max(n);
        right_max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            right_max[i] = std::max(right_max[i + 1], height[i]);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += std::min(left_max[i], right_max[i]) - height[i];
        }
        return ans;
    }
};
动态规划
https://adalovelemon.github.io/blog/posts/content/coursenotes/algorithms/computertalgorithms/dynamicprogramming/
Author
Ada Lovelemon
Published at
2025-04-09

留言板

...
© 2026 Ada Lovelemon Site policy Astro theme powered