动态规划核心思想与经典问题求解
动态规划三要素
解决动态规划问题需遵循以下步骤：
- 状态定义：明确
dp[i]或dp[i][j]的具体含义 - 状态转移方程：建立状态之间的递推关系
- 边界条件与实现：确定初始值，选择递归或迭代方式编码
常见优化策略
- 状态压缩：减少维度，降低空间复杂度
- 滚动数组：仅保留必要的历史状态
- 单调队列/斜率优化：加速状态转移过程
- 记忆化搜索：避免重复计算
记忆化搜索与递推实现
以经典的兔子繁殖问题为例，其本质为斐波那契数列。两种实现方式对比：
方法一：记忆化递归
#include <iostream>
using namespace std;
const int LIMIT = 100;
long long memo[LIMIT + 5] = {0};
long long solve(int month) {
if (month <= 2) return month;
if (memo[month]) return memo[month];
memo[month] = solve(month - 1) + solve(month - 2);
return memo[month];
}
int main() {
int n;
cin >> n;
cout << solve(n) << endl;
return 0;
}方法二：自底向上递推
long long table[105] = {0};
void iterative_solve() {
int n;
cin >> n;
table[1] = 1;
table[2] = 2;
for (int i = 3; i <= n; i++) {
table[i] = table[i-1] + table[i-2];
}
cout << table[n] << endl;
}大整数处理方案
当数值超出 long long 范围时，需自定义大整数类：
#include <vector>
#include <iostream>
using namespace std;
class LargeNumber : public vector<int> {
public:
LargeNumber() { push_back(0); }
LargeNumber(int val) {
push_back(val);
normalize();
}
LargeNumber& operator+=(const LargeNumber& other) {
for (size_t i = 0; i < other.size(); i++) {
if (i >= size()) push_back(other[i]);
else at(i) += other[i];
}
normalize();
return *this;
}
LargeNumber operator+(const LargeNumber& other) {
LargeNumber result(*this);
result += other;
return result;
}
void normalize() {
for (size_t i = 0; i < size(); i++) {
if (at(i) < 10) continue;
if (i == size() - 1) push_back(0);
at(i + 1) += at(i) / 10;
at(i) %= 10;
}
}
};
ostream& operator<<(ostream& out, const LargeNumber& num) {
for (int i = num.size() - 1; i >= 0; i--) {
out << num[i];
}
return out;
}
LargeNumber fib[105];
void big_integer_version() {
int n;
cin >> n;
fib[1] = LargeNumber(1);
fib[2] = LargeNumber(2);
for (int i = 3; i <= n; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
cout << fib[n] << endl;
}Python 简洁实现
Python 天然支持大整数，无需额外处理：
MAX = 100
cache = [0] * (MAX + 5)
def fib_memo(n):
if n <= 2:
return n
if cache[n]:
return cache[n]
cache[n] = fib_memo(n-1) + fib_memo(n-2)
return cache[n]
# 递推版本
def fib_iter(n):
if n <= 2:
return n
dp = [0] * (MAX + 5)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
n = int(input())
print(fib_iter(n))完全背包问题：钱币组合
问题描述：给定 m 种面值的钱币，求凑成 n 元的方案数。
状态设计：ways[i][j] 表示使用前 i 种钱币凑成 j 元的方案数。
状态转移：将方案划分为互斥的两类
- 不使用第
i种钱币：ways[i-1][j] - 至少使用一枚第
i种钱币：ways[i][j-value[i]]
转移方程：ways[i][j] = ways[i-1][j] + ways[i][j-value[i]]
C++ 实现
#include <iostream>
using namespace std;
const int MAX_AMOUNT = 10000;
const int MAX_TYPES = 20;
int coin_val[MAX_TYPES + 5];
int ways[MAX_TYPES + 5][MAX_AMOUNT + 5];
void coin_combination() {
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; i++) {
cin >> coin_val[i];
}
for (int i = 1; i <= m; i++) {
ways[i][0] = 1; // 凑成0元有1种方案（什么都不选）
for (int j = 1; j <= n; j++) {
ways[i][j] = ways[i-1][j]; // 不选第i种
if (j >= coin_val[i]) {
ways[i][j] += ways[i][j - coin_val[i]]; // 选第i种
}
ways[i][j] %= 9973;
}
}
cout << ways[m][n] << endl;
}Python 实现
MOD = 9973
def count_ways(types, amount, values):
# 初始化DP表
dp = [[0] * (amount + 1) for _ in range(types + 1)]
for i in range(1, types + 1):
dp[i][0] = 1 # 边界条件
for j in range(1, amount + 1):
dp[i][j] = dp[i-1][j] # 不选当前钱币
if j >= values[i-1]:
dp[i][j] += dp[i][j - values[i-1]] # 选当前钱币
dp[i][j] %= MOD
return dp[types][amount]
if __name__ == '__main__':
m, n = map(int, input().split())
coins = list(map(int, input().split()))
print(count_ways(m, n, coins))空间优化版本
观察状态转移方程，发现 ways[i][j] 仅依赖于当前行和上一行，可优化为一维数组：
void optimized_version() {
int m, n;
cin >> m >> n;
int val[MAX_TYPES];
for (int i = 0; i < m; i++) cin >> val[i];
int dp[MAX_AMOUNT + 5] = {0};
dp[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = val[i]; j <= n; j++) {
dp[j] += dp[j - val[i]];
dp[j] %= 9973;
}
}
cout << dp[n] << endl;
}