1. 什么是动态规划？

动态规划（Dynamic Programming，简称DP）是一种解决复杂问题的算法思想，它通过将大问题分解为小问题，并存储小问题的解来避免重复计算，从而提高效率。

核心思想：

• 将问题分解为子问题
• 解决子问题
• 通过子问题的解构建原问题的解

2. 为什么使用一维数组？

在动态规划中，我们经常使用数组来存储子问题的解。
本篇文章仅介绍使用一维数组解决简单问题，二维数组虽然稍微复杂但可以显示更多的信息，在复杂问题中更常见。

1. 空间效率高：占用内存更少
2. 代码简洁：实现更简单直观
3. 适合线性问题：很多问题天然适合一维表示

3. 经典示例：斐波那契数列

我们可以从一个简单的例子开始，理解一维数组在DP中的应用。

问题描述：
计算第n个斐波那契数：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n ≥ 2)

暴力递归（低效）：

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

一维数组DP解法：

int fibDP(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 fibOptimized(int n) {
    if (n <= 1) return n;
    int prev2 = 0;  // dp[i-2]
    int prev1 = 1;  // dp[i-1]
    int current;     // dp[i]
    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}

4. 爬楼梯问题

问题描述：
假设你正在爬楼梯，每次可以爬1阶或2阶。有多少种不同的方法可以爬到第n阶？
该类题目的解题方法与上一种大体一致。
DP分析：

1. 定义状态：dp[i] 表示爬到第i阶的方法数
2. 状态转移：dp[i] = dp[i-1] + dp[i-2]
3. 初始条件：dp[0] = 1, dp[1] = 1

代码实现：

int climbStairs(int n) {
    if (n <= 1) return 1;
    vector<int> dp(n + 1);
    dp[0] = 1;  // 起点，1种方法（不动）
    dp[1] = 1;  // 爬1阶，1种方法
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

5. 零钱兑换问题

问题描述：
给定不同面额的硬币和一个总金额，计算凑成总金额所需的最少硬币数。

DP分析：

1. 定义状态：dp[i] 表示凑成金额i所需的最少硬币数
2. 状态转移：dp[i] = min(dp[i], dp[i-coin] + 1)
3. 初始条件：dp[0] = 0，其他初始化为一个大数

代码实现：

int coinChange(vector<int>& coins, int amount) {
    // 初始化dp数组，用一个大数表示不可达
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;  // 金额为0时不需要硬币
    // 遍历所有金额
    for (int i = 1; i <= amount; i++) {
        // 尝试每种硬币
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

6. 一维DP的通用解题步骤

步骤1：定义状态：

确定dp数组的含义，通常：

• dp[i]：表示以位置i结尾的某种最优解
• dp[i]：表示处理到第i个元素时的结果

步骤2：找出状态转移方程：

这是DP的核心，需要分析问题如何从子问题推导：

• 斐波那契：dp[i] = dp[i-1] + dp[i-2]
• 爬楼梯：dp[i] = dp[i-1] + dp[i-2]
• 零钱兑换：dp[i] = min(dp[i], dp[i-coin] + 1)

步骤3：确定初始条件：

设置dp数组的初始值：

• 通常dp[0]或dp[1]有特殊含义
• 可能需要初始化多个位置

步骤4：确定遍历顺序：

根据状态转移方程决定遍历方向：

• 自底向上：从前往后遍历
• 自顶向下：递归+记忆化

步骤5：返回结果：

返回dp数组的最后一个元素或特定位置的元素。

7. 常见问题类型

类型1：线性序列问题

• 最长递增子序列
• 最大子数组和
• 打家劫舍问题

类型2：背包问题（一维优化）

• 0-1背包（需要逆序遍历）
• 完全背包（正序遍历）

类型3：字符串匹配

• 编辑距离（需要二维，但可优化为一维）

8. 实战技巧

技巧1：空间优化：

很多一维DP可以优化为使用几个变量：

// 优化前
vector<int> dp(n + 1);
// 优化后（如斐波那契）
int prev2, prev1, current;

技巧2：边界处理：

// 检查数组越界
if (i >= coin) {
    dp[i] = min(dp[i], dp[i-coin] + 1);
}

技巧3：初始化技巧：

// 用大数初始化表示"无穷大"
vector<int> dp(n + 1, INT_MAX / 2);
dp[0] = 0;

技巧4：遍历顺序：

// 0-1背包：逆序遍历（防止重复使用）
for (int i = amount; i >= coin; i--) {
    dp[i] = max(dp[i], dp[i-coin] + value);
}

// 完全背包：正序遍历（允许重复使用）
for (int i = coin; i <= amount; i++) {
    dp[i] = max(dp[i], dp[i-coin] + value);
}

9. 总结

一维数组在动态规划中应用广泛，掌握它需要：

1. 理解状态定义：明确dp[i]的含义
2. 推导转移方程：找到问题的最优子结构
3. 注意边界条件：正确处理初始状态
4. 考虑空间优化：在必要时减少内存使用

记住：动态规划的核心思想是"记住过去，避免重复计算"。一维数组正是实现这一思想的简洁工具。