斐波那契数列模型
斐波那契数列是动态规划的入门模型，其核心思想是当前状态由前几个状态线性组合而成。
- 状态定义：通常使用一维
dp数组，dp[i]表示第i个位置的数值。 - 状态转移方程：
dp[i] = dp[i-1] + dp[i-2] + ... - 初始化：根据递推公式，需要预先定义好前几个无法被推导出的状态值。
经典例题：第 N 个泰波那契数 (LeetCode 1137)
泰波那契序列 Tn 定义为：T0=0,T1=1,T2=1，且在 n≥0 的条件下 Tn+3=Tn+Tn+1+Tn+2。
C++ 优化代码 (滚动数组/状态压缩)
对于斐波那契类型的题目，由于 dp[i] 的计算只依赖于前几个固定状态，可以使用滚动数组（状态压缩）将空间复杂度从 O(N) 优化到 O(1)。
C++
#include <iostream>
class Solution {
public:
int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
// 使用状态压缩，仅保留最近的三个状态
int a = 0, b = 1, c = 1;
int d; // 用于计算新状态
for (int i = 3; i <= n; ++i) {
d = a + b + c;
// 状态向前滚动
a = b;
b = c;
c = d;
}
return c; // 最终结果存储在 c 中
}
};
// int main() {
// Solution sol;
// std::cout << sol.tribonacci(25) << std::endl; // 输出: 1389537
// return 0;
// }
路径问题
路径问题通常涉及在二维网格中，从起点到终点寻找特定路径（如总数、最小代价等）。
- 状态定义：
dp[i][j]通常表示到达网格位置(i, j)时的路径属性（如路径总数）。 - 状态转移方程：
dp[i][j]的值通常由其上方dp[i-1][j]和左方dp[i][j-1]的状态转移而来。 - 初始化：通常需要初始化网格的边界条件，例如第一行和第一列的路径值。
经典例题：不同路径 (LeetCode 62)
一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或向右移动一步。问总共有多少条不同的路径可以到达网格的右下角。
C++ 优化代码 (空间优化)
观察到 dp[i][j] 的计算只依赖于当前行和上一行的数据，因此可以将二维 dp 数组压缩为一维。
C++
#include <iostream>
#include <vector>
class Solution {
public:
int uniquePaths(int m, int n) {
// 空间优化：使用一维数组
std::vector<int> dp(n, 1); // 初始化第一行全为1
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
// 当前格的路径数 = 上方格的路径数 + 左方格的路径数
// dp[j] 在更新前是上一行的值 (dp[i-1][j])
// dp[j-1] 是当前行前一列的值 (dp[i][j-1])
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
};
// int main() {
// Solution sol;
// std::cout << sol.uniquePaths(3, 7) << std::endl; // 输出: 28
// return 0;
// }
简单多状态 DP
当单个状态无法完整描述问题时，需要定义多个状态。这类问题中，每个位置 i 可能处于不同的状态（例如，持有/不持有，接/不接），需要用多个 dp 数组或 dp 数组的多个维度来表示。
- 状态定义：
dp[i][state]表示在位置i处于state状态时的最优值。例如，f[i]表示在i处进行某操作的最优值，g[i]表示在i处不进行该操作的最优值。 - 状态转移方程：根据不同状态间的依赖关系分别建立转移方程。
- 初始化：根据问题的初始条件，初始化
dp数组在i=0时的各个状态值。
经典例题：按摩师 (LeetCode 面试题 17.16)
一个按摩师不能接受相邻的预约。给定一个代表预约时长的数组，求能够获得的最长总预约时长。
C++ 优化代码 (状态压缩)
由于 dp[i] 只依赖于 dp[i-1]，可以将空间复杂度优化到 O(1)。
C++
#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
int massage(std::vector<int>& nums) {
if (nums.empty()) {
return 0;
}
if (nums.size() == 1) {
return nums[0];
}
// f: 接受当前预约的最大时长
// g: 不接受当前预约的最大时长
int g = 0, f = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
int temp_g = std::max(f, g); // 新的g[i]
int temp_f = g + nums[i]; // 新的f[i]
g = temp_g;
f = temp_f;
}
return std::max(f, g);
}
};
// int main() {
// Solution sol;
// std::vector<int> nums = {2, 7, 9, 3, 1};
// std::cout << sol.massage(nums) << std::endl; // 输出: 12
// return 0;
// }
子数组/子串系列
子数组或子串问题要求处理连续的元素片段。
- 状态定义：
dp[i]通常表示以nums[i]结尾的子数组所具有的某种性质（如最大和、最大乘积）。 - 状态转移方程：
dp[i]的值通常与dp[i-1]和nums[i]本身有关。 - 返回值：最终结果不一定是
dp[n-1]，因为最大/最优的子数组可能在任何位置结束，所以需要在遍历过程中记录全局最优解。
经典例题：最大子数组和 (LeetCode 53)
找出一个具有最大和的连续子数组，并返回其最大和。
C++ 优化代码 (状态压缩)
dp[i] 的计算只依赖于 dp[i-1]，可以进行状态压缩。
C++
#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
int maxSubArray(std::vector<int>& nums) {
if (nums.empty()) return 0;
int max_so_far = nums[0];
int current_max = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
// 状态转移：决定是“自立门户”还是“加入组织”
// 如果前一个子数组的和是负数，则不如从当前元素开始重新计算
current_max = std::max(nums[i], current_max + nums[i]);
// 更新全局最大值
max_so_far = std::max(max_so_far, current_max);
}
return max_so_far;
}
};
// int main() {
// Solution sol;
// std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
// std::cout << sol.maxSubArray(nums) << std::endl; // 输出: 6
// return 0;
// }
子序列问题
子序列问题与子数组不同，它处理的元素不要求连续。
- 状态定义：
dp[i]通常表示以nums[i]结尾的子序列所具有的性质（例如，最长递增子序列的长度）。 - 状态转移方程：
dp[i]的计算通常需要遍历j从0到i-1的所有dp[j]，找出满足条件的dp[j]来更新dp[i]。 - 初始化：通常将
dp数组的所有元素初始化为一个基本值（如 1）。
经典例题：最长递增子序列 (LeetCode 300)
找到一个整数数组中最长严格递增子序列的长度。
C++ 优化代码 (贪心 + 二分查找)
此题存在一个更优的解法，时间复杂度为 O(NlogN)。维护一个“耐心排序”的 tails 数组，tails[i] 存储长度为 i+1 的所有递增子序列中末尾元素的最小值。
C++
#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
int lengthOfLIS(std::vector<int>& nums) {
if (nums.empty()) return 0;
std::vector<int> tails;
tails.push_back(nums[0]);
for (size_t i = 1; i < nums.size(); ++i) {
if (nums[i] > tails.back()) {
// 如果当前元素比所有已知递增子序列的末尾都大，
// 它可以扩展最长的那个序列，形成一个更长的序列。
tails.push_back(nums[i]);
} else {
// 否则，在 tails 数组中找到第一个大于或等于 nums[i] 的元素，
// 并用 nums[i] 替换它。这表示我们找到了一个长度相同但末尾更小的递增子序列。
auto it = std::lower_bound(tails.begin(), tails.end(), nums[i]);
*it = nums[i];
}
}
return tails.size();
}
};
// int main() {
// Solution sol;
// std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
// std::cout << sol.lengthOfLIS(nums) << std::endl; // 输出: 4
// return 0;
// }
回文串问题
回文串问题关注字符串中正读和反读都相同的子串或子序列。
- 状态定义：通常使用二维
dp数组，dp[i][j]表示字符串s中从索引i到j的子串s[i...j]是否为回文串。 - 状态转移方程：
dp[i][j]的真假取决于s[i] == s[j]以及dp[i+1][j-1]是否为真。 - 填表顺序：由于
dp[i][j]依赖于dp[i+1][j-1]（左下角的值），遍历时需要保证左下角的值先被计算。通常采用从下到上、从左到右的遍历顺序。
经典例题：最长回文子串 (LeetCode 5)
找到一个字符串中最长的回文子串。
C++ 优化代码 (中心扩展法)
动态规划的空间和时间复杂度均为 O(N2)。中心扩展法空间复杂度更优，为 O(1)。它以每个字符或两个字符之间为中心，向两边扩展，寻找最长的回文串。
C++
#include <iostream>
#include <string>
#include <algorithm>
class Solution {
public:
std::string longestPalindrome(std::string s) {
if (s.length() < 1) return "";
int start = 0, max_len = 1;
for (int i = 0; i < s.length(); ++i) {
// 奇数长度的回文串
int len1 = expandAroundCenter(s, i, i);
// 偶数长度的回文串
int len2 = expandAroundCenter(s, i, i + 1);
int len = std::max(len1, len2);
if (len > max_len) {
start = i - (len - 1) / 2;
max_len = len;
}
}
return s.substr(start, max_len);
}
private:
int expandAroundCenter(const std::string& s, int left, int right) {
while (left >= 0 && right < s.length() && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1;
}
};
// int main() {
// Solution sol;
// std::cout << sol.longestPalindrome("babad") << std::endl; // 输出: "bab" 或 "aba"
// return 0;
// }
两个数组的 DP 问题
这类问题涉及两个输入数组（或字符串），状态定义需要同时考虑两个数组的索引。
- 状态定义：
dp[i][j]表示第一个数组的前i个元素和第二个数组的前j个元素之间的某种关系（如最长公共子序列长度）。 - 状态转移方程：
dp[i][j]的计算通常依赖于dp[i-1][j]、dp[i][j-1]和dp[i-1][j-1]。 - 初始化：通常需要处理一个或两个数组为空的情况，这可以通过扩展
dp表的大小（增加一行一列）来简化。
经典例题：最长公共子序列 (LeetCode 1143)
返回两个字符串的最长公共子序列的长度。
C++ 优化代码 (空间优化)
dp[i][j] 的计算只依赖于上一行和当前行的数据，可以将空间复杂度从 O(MN) 优化到 O(min(M,N))。
C++
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
class Solution {
public:
int longestCommonSubsequence(std::string text1, std::string text2) {
int m = text1.length();
int n = text2.length();
// 确保 dp 数组大小为较小维度，节省空间
if (m < n) {
return longestCommonSubsequence(text2, text1);
}
std::vector<int> dp(n + 1, 0);
for (int i = 1; i <= m; ++i) {
int prev_row_prev_col = 0; // 模拟 dp[i-1][j-1]
for (int j = 1; j <= n; ++j) {
int temp = dp[j]; // 临时保存 dp[i-1][j]
if (text1[i - 1] == text2[j - 1]) {
dp[j] = prev_row_prev_col + 1;
} else {
dp[j] = std::max(dp[j], dp[j - 1]);
}
prev_row_prev_col = temp;
}
}
return dp[n];
}
};
// int main() {
// Solution sol;
// std::cout << sol.longestCommonSubsequence("abcde", "ace") << std::endl; // 输出: 3
// return 0;
// }
0/1 背包问题
给定一组物品，每个物品只有一个，有各自的重量和价值。在限定的总重量内，如何选择物品使得总价值最高。
- 状态定义：
dp[i][j]表示从前i个物品中选择，放入容量为j的背包中所能获得的最大价值。 - 状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])。这代表两种决策：不放第i个物品，或放第i个物品。
经典例题：分割等和子集 (LeetCode 416)
判断一个只包含正整数的非空数组是否可以被分割成两个子集，使得两个子集的元素和相等。这可以转化为一个 0/1 背包问题：能否从数组中选出一些数，其和恰好等于数组总和的一半。
C++ 优化代码 (空间优化)
可以将 dp 数组压缩到一维。关键在于内层循环必须从后往前遍历，以保证在计算 dp[j] 时，所依赖的 dp[j - weight[i]] 仍然是上一轮（i-1）的状态。
C++
#include <iostream>
#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] (不选num) || dp[j - num] (选num)
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
};
// int main() {
// Solution sol;
// std::vector<int> nums = {1, 5, 11, 5};
// std::cout << std::boolalpha << sol.canPartition(nums) << std::endl; // 输出: true
// return 0;
// }
完全背包问题
与 0/1 背包不同，完全背包问题中的每种物品可以无限次地选取。
- 状态定义：同 0/1 背包。
- 状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i][j - weight[i]] + value[i])。注意，第二个选项是dp[i]而非dp[i-1]，这表示在考虑第i个物品时，我们可以在已经放过第i个物品的背包中继续放。
经典例题：零钱兑换 (LeetCode 322)
给你一个整数数组 coins 表示不同面额的硬币，以及一个整数 amount 表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。
C++ 优化代码 (空间优化)
同样可以压缩到一维。与 0/1 背包不同的是，内层循环必须从前往后遍历，以确保 dp[j - coin] 是本轮（i）更新过的值，这恰好体现了物品可重复选取的特性。
C++
#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
int coinChange(std::vector<int>& coins, int amount) {
int max_val = amount + 1;
std::vector<int> dp(amount + 1, max_val);
dp[0] = 0;
for (int coin : coins) {
for (int j = coin; j <= amount; ++j) {
dp[j] = std::min(dp[j], dp[j - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
// int main() {
// Solution sol;
// std::vector<int> coins = {1, 2, 5};
// std::cout << sol.coinChange(coins, 11) << std::endl; // 输出: 3
// return 0;
// }