CC++ & Algorithm

一维动态规划

困难0
语言版本：C++
概述：一维动态规划只用一维数组记录状态，解决如爬楼梯、最大子段和等问题。

一维动态规划入门：从爬楼梯到最大子段和

动态规划（Dynamic Programming，简称 DP）是一种通过把大问题拆成小问题，再利用小问题的答案来逐步推出大问题答案的方法。一维动态规划特别简单——我们只需要一个一维数组（比如 Python 里的列表）来记录每一步的中间结果，然后沿着一条“直线”从前往后或从后往前递推。它很适合解决像“爬楼梯”、“最大子段和”这类问题，它们都只有一个方向的变化。

? 核心概念：状态、转移、边界

要写好一维 DP，必须抓住三个东西：

  1. 状态（State）：数组 dp[i] 表示什么？比如“爬到第 i 级台阶有几种方法”或“以第 i 个数字结尾的最大连续和”。你要清楚每一个 dp[i] 的含义。
  2. 转移方程（Transition）：如何从前面的状态推导出 dp[i]？比如 dp[i] = dp[i-1] + dp[i-2]。
  3. 边界条件（Base Case）：最小的几个状态的值，比如 dp[1]、dp[2] 必须提前手动设好，不然没法递推。

想象你在记录每天的零花钱：每天你都会收到一些钱（新数据），然后你需要知道到今天为止一共攒了多少钱（累计和），这就是一维 DP。状态 dp[i] 表示到第 i 天的总零花钱，转移是 dp[i] = dp[i-1] + 今天的钱，边界是 dp[0]=0。

?‍♂️ 例子1：爬楼梯

问题描述：一个人爬楼梯，每次可以跨 1 级或 2 级台阶。问爬到第 n 级台阶有多少种不同的爬法？

思路：要想到达第 i 级台阶，最后一步要么是从第 i-1 级跨 1 步，要么是从第 i-2 级跨 2 步。所以爬到第 i 级的方法数 = 爬到第 i-1 级的方法数 + 爬到第 i-2 级的方法数。

状态定义：dp[i] 表示爬到第 i 级台阶的爬法总数。

边界：

  • dp[1] = 1（只有一种爬法：1 步）
  • dp[2] = 2（两种：一次 2 步，或两次 1 步）

转移：dp[i] = dp[i-1] + dp[i-2]（对于 i ≥ 3）

代码（每一步都加了中文注释）：

def climb_stairs(n):
    # 如果台阶数很少，直接返回边界结果
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    # 创建一个长度为 n+1 的列表，下标0~n，dp[0]不用
    dp = [0] * (n + 1)
    dp[1] = 1   # 爬到第1级有1种方法
    dp[2] = 2   # 爬到第2级有2种方法
    
    # 从第3级开始逐一计算，直到第n级
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # 到达i的方法数 = 到i-1 + 到i-2
    
    return dp[n]

# 测试：爬5级台阶，应该有8种爬法
print(climb_stairs(5))   # 输出 8

生活联想：这就像你每天上学，可以走楼梯或电梯（只能选一种）。楼梯一次跨1级，电梯一次跨2级。问上到5楼有多少种不同的方式？你可以在纸上画一画，会发现确实有8种。

? 例子2：最大子段和

问题描述：给你一个整数数组（可能有负数），请找出一个连续的子数组（子段），使它的和最大。比如 [-2, 1, -3, 4, -1, 2]，最大子段是 [4, -1, 2]，和为5。

思路：我们关心的是“以第 i 个数字结尾的最大连续和”。因为子段必须连续，所以对于每个位置 i，要么把它接到前一个位置 i-1 的连续段后面，要么自己重新开始一个新段。

状态定义：dp[i] 表示以 nums[i]（第 i 个元素）结尾的连续子数组的最大和。

边界：dp[0] = nums[0]（第一个元素只能自己单独一段）。

转移：

  • 如果 dp[i-1] + nums[i] 比 nums[i] 大，说明接上前面的段更好：dp[i] = dp[i-1] + nums[i]
  • 否则，不如自己单干：dp[i] = nums[i]
  • 合并为一句：dp[i] = max(dp[i-1] + nums[i], nums[i])

代码：

def max_subarray(nums):
    n = len(nums)
    if n == 0:          # 如果数组是空的，最大和为0
        return 0
    
    dp = [0] * n        # dp[i] 表示以 nums[i] 结尾的最大子段和
    dp[0] = nums[0]     # 第一个元素只能自己一段
    max_sum = dp[0]     # 记录全局最大值
    
    for i in range(1, n):
        # 要么把 nums[i] 接到前面的段后，要么从头开始
        dp[i] = max(dp[i - 1] + nums[i], nums[i])
        # 更新全局最大和
        if dp[i] > max_sum:
            max_sum = dp[i]
    
    return max_sum

# 测试
print(max_subarray([-2, 1, -3, 4, -1, 2]))   # 输出 5

生活联想：假设你连续6天卖零食，每天赚的钱分别是 -2元、1元、-3元、4元、-1元、2元。你想找出连续几天里总利润最高的一天段。从第四天到第六天（4 -1 +2 =5）就是最好的一段。如果你亏本的一天（比如 -3）接上之前赚的，反而拉低利润，不如当天重新开始。

⚠️ 新手容易犯的4个错误

  1. 忘记处理边界条件

    • 例如爬楼梯时 n=1 或 n=2 没有直接返回，会导致数组越界或错误结果。
    • 最大子段和空数组没考虑，直接取 nums[0] 会报错。

  2. 数组长度拿不准

    • 爬楼梯中 dp 长度设为 n+1（下标从0到n），但循环时却用了 n 或 n-1，导致索引错误。
    • 要记住：如果 dp 下标从0开始，那么 dp[i] 对应第 i 个元素，长度 n 即可；如果下标从1开始，长度要 n+1。

  3. 状态转移方程写反或漏掉条件

    • 比如最大子段和里写成 dp[i] = dp[i-1] + nums[i] 而忘记取最大值，结果会一直是累计和，不能重新开始。
    • 爬楼梯时写成 dp[i] = dp[i-1] + dp[i] 显然不对。

  4. 不理解 dp[i] 的含义，导致更新错误

    • 有人把爬楼梯的 dp[i] 理解成“到达第 i 级必须走多少步”，而实际上它表示“方法数”，完全不同。
    • 一定要先想清楚每个 dp 值代表什么，再写代码。

? 完整可运行的示例代码

把两个函数放在一起，加上更多测试：

# 一维动态规划示例：爬楼梯 和 最大子段和

def climb_stairs(n):
    # 爬楼梯：返回爬到第n级的方法数
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    dp = [0] * (n + 1)   # dp[i]：爬到第i级的方法数
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def max_subarray(nums):
    # 最大子段和：返回连续子数组的最大和
    n = len(nums)
    if n == 0:
        return 0
    
    dp = [0] * n          # dp[i]：以nums[i]结尾的最大子段和
    dp[0] = nums[0]
    max_sum = dp[0]
    for i in range(1, n):
        dp[i] = max(dp[i - 1] + nums[i], nums[i])
        if dp[i] > max_sum:
            max_sum = dp[i]
    return max_sum

# ========== 测试 ==========
if __name__ == "__main__":
    # 测试爬楼梯
    print("爬5级台阶的方法数：", climb_stairs(5))   # 8
    print("爬10级台阶的方法数：", climb_stairs(10))  # 89
    
    # 测试最大子段和
    arr1 = [-2, 1, -3, 4, -1, 2]
    print("数组", arr1, "的最大子段和：", max_subarray(arr1))  # 5
    
    arr2 = [5, 4, -1, 7, 8]
    print("数组", arr2, "的最大子段和：", max_subarray(arr2))  # 23（全部加起来）

运行这段代码，你会得到正确的输出结果。

? 接下来可以学什么？

一维动态规划只是起点，掌握了状态和转移的思想后，你可以挑战更多问题：

  • 斐波那契数列：和爬楼梯几乎一样，只不过边界是 dp[0]=0, dp[1]=1。
  • 零钱兑换（一维）：给定几种面额的硬币，凑出总金额的最少硬币数——状态 dp[i] 表示凑出 i 元的最少硬币数。
  • 背包问题：一维的 0-1 背包（其实也常用一维数组优化空间）。
  • 二维 DP：比如机器人从左上角走到右下角有多少条路径，需要用二维数组记录状态。

动态规划有一个实用的“五步法”：
① 确定状态（dp[i] 代表什么）
② 推导转移方程
③ 设置边界条件
④ 确定计算顺序（通常是从小到大）
⑤ 输出答案

按照这个套路，再难的 DP 题也能一步步拆解。加油！

例题精讲

1单选题

爬楼梯问题：小明每次可以爬1级或2级台阶，爬到第n级台阶有多少种不同的方法？用一维动态规划求解，定义dp[i]为爬到第i级台阶的方法数。则状态转移方程是？

Adp[i] = dp[i-1] + dp[i-2]
Bdp[i] = dp[i-1] * dp[i-2]
Cdp[i] = dp[i-1] + 1
Ddp[i] = dp[i-1] + dp[i-2] + dp[i-3]
2单选题

最大子段和问题：给定数组[-2,1,-3,4,-1,2,1,-5,4]，求连续子数组的最大和。使用一维DP，定义dp[i]为以第i个元素结尾的最大子段和，则最终答案为？

A6
B4
C7
D5
3判断题

一维动态规划中，状态转移方程只能依赖于前一个状态，不能依赖更早的状态。

4填空题
打家劫舍问题：给定一个非负整数数组nums，不能偷相邻的两家，求能偷到的最大金额。请补全下面一维DP代码。

def rob(nums):
    if not nums:
        return 0
    n = len(nums)
    if n == 1:
        return nums[0]
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, n):
        dp[i] = max(___, dp[i-1])
    return dp[-1]
5填空题
斐波那契数列：求第n项（n从0开始），F(0)=0, F(1)=1。用一维DP（空间优化版）实现，补全代码。

def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(___, n + 1):
        a, b = b, ___ + ___
    return ___