动态规划的基本条件

动态规划（Dynamic Programming, DP）是一种用于解决复杂问题的算法设计方法，通常用于优化问题。要使用动态规划，问题必须满足以下三个基本条件：

最优子结构
- 要解决一个大问题，我们可以先解决其更小的子问题
- 大问题的最优解可以通过子问题的最优解来构建
无后效性
- 已经求解的子问题，不会再受到后续决策的影响
子问题重叠
- 问题可以分解为多个子问题
- 这些子问题在求解过程中会被多次计算

例如，斐波那契数列的计算满足上述条件：

最优子结构： $F(n) = F(n-1) + F(n-2)$
无后效性： $F(n)$ 的计算只依赖于 $F(n-1)$ 和 $F(n-2)$ ，不会受到后续计算 $F(i),\,i>n$ 的影响
子问题重叠： $F(n-1)$ 和 $F(n-2)$ 会被多次计算

动态规划的两种实现方式

动态规划通常有两种实现方式：自顶向下的记忆化搜索法和自底向上的递推法。

自顶向下的记忆化搜索法（Memoization）

通过递归的方式自顶向下地解决问题
使用一个数据结构（通常是数组或哈希表）来存储已经计算的子问题的结果
在递归过程中，先检查子问题是否已经计算过，如果计算过则直接返回结果，否则进行计算并存储结果
适用于问题规模较大且递归深度较浅的情况例如，计算斐波那契数列的记忆化搜索法实现如下：

#include <bits/stdc++.h>
using namespace std;

#define MAXN (100)
int memo[MAXN]; // 用于存储已经计算的斐波那契数

int fibonacci(int n) {
    if (n <= 1) return n; // 基本情况
    if (memo[n] != -1) return memo[n]; // 如果已经计算过，直接返回结果
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2); // 计算并存储结果
    return memo[n];
}

int main() {
    int n = 10; // 计算第10个斐波那契数
    memset(memo, -1, sizeof(memo)); // 初始化memo数组
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

自底向上的递推法（Tabulation）

通过迭代的方式自底向上地解决问题
通常使用一个数组来存储子问题的结果，从最小的子问题开始，逐步构建到原问题
适用于问题规模较大且递归深度较深的情况例如，计算斐波那契数列的递推法实现如下：

#include <bits/stdc++.h>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) return n; // 基本情况
    vector<int> dp(n + 1); // 用于存储斐波那契数
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 计算并存储结果
    }
    return dp[n];
}
int main() {
    int n = 10; // 计算第10个斐波那契数
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

动态规划的四个步骤

无论使用哪种实现方式，动态规划均需要遵循以下四个步骤：

定义状态：确定问题的动态规划表示，通常使用dp数组的元素来表示子问题的解（这一步往往很难！）
状态转移方程：找出状态之间的关系，通过递推方程来表示，包含解析式和相应的变量取值范围（这一步往往很难！）
边界条件：确定初始状态的值，通常是最小子问题的解
答案的表示：确定最终答案的位置，如dp数组的最后一个元素或特定的位置的值注意：动态规划题的原始数据下标一般从1开始，更方便边界条件。

例如，计算斐波那契数列第n个数的四个步骤如下：

定义状态：令 dp[i] 表示第 i 个斐波那契数
状态转移方程：dp[i] = dp[i-1] + dp[i-2]，其中 i >= 2
边界条件：dp[0] = 0，dp[1] = 1
答案的表示：最终答案为 dp[n]

经典例题（但很重要！）

最长公共子序列

题目：

给定一个长度为 $n$ 的序列 $A$ 和一个长度为 $m$ 的序列 $B$ （其中 $n, m \leq 5000$ ），请找出一个最长的序列，使得该序列既是 $A$ 的子序列，也是 $B$ 的子序列。输入：两个字符串 $A$ 和 $B$ 。输出：最长公共子序列的长度。

分析：

定义状态：令 dp[i][j] 表示序列 A 的前 i 个元素和序列 B 的前 j 个元素的最长公共子序列的长度。
状态转移方程：
- 如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
- 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
边界条件：
- dp[0][j] = 0，表示当 A 为空时，最长公共子序列长度为 0
- dp[i][0] = 0，表示当 B 为空时，最长公共子序列长度为 0
答案的表示：最终答案为 dp[n][m]，即序列 A 的前 n 个元素和序列 B 的前 m 个元素的最长公共子序列的长度。

解答：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
int dp[MAXN][MAXN]; // dp数组
string A, B; // 输入的两个序列

int main() {
    cin >> A >> B; // 读取输入序列
    int n = A.size(), m = B.size();
    // 初始化dp数组
    for (int i = 0; i <= n; ++i) dp[i][0] = 0;
    for (int j = 0; j <= m; ++j) dp[0][j] = 0;
    // 填充dp数组
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1; // 字符相同，长度加1
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 字符不同，取最大值
            }
        }
    }
    cout << "Length of Longest Common Subsequence: " << dp[n][m] << endl; // 输出结果
    return 0;
}

最长非降子序列

题目：

给定一个长度为 $n$ 的序列 $a$ （ $n \leq 5000$ ），求出一个最长的 $a$ 的子序列，满足该子序列的后一个元素不小于前一个元素。输入：先输入正整数 $n$ ，再输入一个长度为 $n$ 的序列 $a$ 。输出：最长非降子序列的长度。

该题有两种方法分析，其中第一种方法为dp，时间复杂度为 $O(n^2)$ ；第二种方法为贪心+二分，时间复杂度为 $O(n\log n)$ 。

方法1：dp

分析：

定义状态：令 dp[i] 表示以 a[i] 结尾的最长非降子序列的长度。
状态转移方程：对于每个 i，遍历 j 从 0 到 i-1：如果 a[j] <= a[i]，则 dp[i] = max(dp[i], dp[j] + 1)。
边界条件： dp[i] = 1，表示每个元素自身可以作为一个长度为 1 的非降子序列
答案的表示：最终答案为 max(dp[i])，其中 0 <= i < n。

解答：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
int dp[MAXN]; // dp数组
int a[MAXN]; // 输入的序列

int main() {
    int n;
    cin >> n; // 读取序列长度
    for (int i = 0; i < n; ++i) {
        cin >> a[i]; // 读取序列元素
        dp[i] = 1; // 初始化dp数组，每个元素自身可以作为长度为1的非降子序列
    }
    // 填充dp数组
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] <= a[i]) { // 如果a[j]不大于a[i]
                dp[i] = max(dp[i], dp[j] + 1); // 更新dp[i]
            }
        }
    }
    int ans = *max_element(dp, dp + n); // 找到最长非降子序列的长度
    cout << ans << endl; // 输出结果
    return 0;
}

方法2：贪心+二分

详见：（省略）

The Basics of Dynamic Programming 动态规划基础