代码随想录刷题 Day 32丨动态规划理论基础

引言

动态规划（Dynamic Programming，DP）是一种常用的算法设计技巧，尤其适用于具有重叠子问题和最优子结构性质的问题。在本篇文章中，我们将探讨几个经典的动态规划问题，包括斐波那契数、爬楼梯以及最小花费爬楼梯。这些问题不仅在算法竞赛中经常出现，也在实际应用中具有重要意义。

一、动态规划的基础

1.1 动态规划的定义

动态规划是一种通过将复杂问题分解为更简单的子问题来解决问题的策略。动态规划的关键在于记忆化存储（Memoization）或表格填充（Tabulation）方法，用以避免重复计算，从而降低时间复杂度。

1.2 动态规划的应用场景

动态规划广泛应用于以下场景：

• 最短路径问题
• 最优资源分配
• 股票买卖问题
• 组合问题
• 字符串匹配

1.3 动态规划的步骤

1. 定义状态：确定需要保存的信息。
2. 确定转移方程：找出状态之间的关系。
3. 设定边界条件：为递归或迭代过程设定初始条件。
4. 计算并保存结果：根据转移方程计算出所需结果。

二、经典动态规划问题分析

2.1 509. 斐波那契数

2.1.1 问题描述

斐波那契数列是一个经典的数列，其定义为：

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

要求计算第 n 个斐波那契数。

2.1.2 状态定义

定义状态 dp[n] 为第 n 个斐波那契数。

2.1.3 转移方程

根据斐波那契数的定义，可以得出：

$$dp[n] = dp[n-1] + dp[n-2]$$

2.1.4 边界条件

• dp[0] = 0
• dp[1] = 1

2.1.5 实现代码

pythonCopy Code
def fib(n: int) -> int:
    if n == 0:
        return 0
    elif n == 1:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

2.1.6 示例

• 输入：fib(5)
• 输出：5 （斐波那契数列为 [0, 1, 1, 2, 3, 5]）

2.2 70. 爬楼梯

2.2.1 问题描述

假设你正在爬楼梯。需要 n 阶楼梯，每次可以爬 1 阶或 2 阶。请计算有多少种不同的方法可以爬到楼梯的顶部。

2.2.2 状态定义

定义状态 dp[i] 为到达第 i 阶的不同方法数。

2.2.3 转移方程

• 每到达第 i 阶，可以从 i-1 阶或 i-2 阶跳上来，因此：

$$dp[i] = dp[i-1] + dp[i-2]$$

2.2.4 边界条件

• dp[0] = 1 （0 阶楼梯，只有一种方式，即不动）
• dp[1] = 1 （1 阶楼梯，也只有一种方式）

2.2.5 实现代码

pythonCopy Code
def climbStairs(n: int) -> int:
    if n == 0:
        return 1
    elif n == 1:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

2.2.6 示例

• 输入：climbStairs(3)
• 输出：3 （有三种方式：[1, 1, 1], [1, 2], [2, 1]）

2.3 746. 使用最小花费爬楼梯

2.3.1 问题描述

每次爬楼梯时需要支付费用，给定一个费用数组 cost，请计算到达楼梯顶部的最小花费。

2.3.2 状态定义

定义状态 dp[i] 为到达第 i 阶所需的最小花费。

2.3.3 转移方程

• 从 i-1 或 i-2 阶到达第 i 阶的最小花费：

$$dp[i] = cost[i] + \min(dp[i-1], dp[i-2])$$

2.3.4 边界条件

• dp[0] = cost[0]
• dp[1] = cost[1]

2.3.5 实现代码

pythonCopy Code
def minCostClimbingStairs(cost: list[int]) -> int:
    n = len(cost)
    if n == 0:
        return 0
    elif n == 1:
        return cost[0]
    dp = [0] * n
    dp[0], dp[1] = cost[0], cost[1]
    for i in range(2, n):
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
    return min(dp[-1], dp[-2])

2.3.6 示例

• 输入：minCostClimbingStairs([10, 15, 20])
• 输出：15 （选择第 1 阶，即 15）

三、动态规划综合实例

在实际应用中，动态规划的思想常用于解决最优路径、资源分配等问题。接下来，我们将通过一个综合实例来展示动态规划的灵活性。

3.1 问题背景

假设有一座城市，有多个景点需要游览，每个景点之间有不同的交通费用和游玩时间。游客希望在有限的时间内，游览尽可能多的景点，并且总费用不超过预算。

3.2 问题建模

1. 定义状态：dp[i][j] 表示在预算为 j，时间为 i 的情况下能够游览的最多景点数。
2. 转移方程：
   • 不游览当前景点：dp[i][j] = dp[i][j]
   • 游览当前景点：dp[i][j] = max(dp[i - time][j - cost] + 1, dp[i][j])
3. 边界条件：如果没有预算或时间，游览景点数为 0。

3.3 实现代码

pythonCopy Code
def maxAttractions(attractions: list[tuple[int, int]], time: int, budget: int) -> int:
    dp = [[0] * (budget + 1) for _ in range(time + 1)]
    
    for cost, t in attractions:
        for i in range(time, t - 1, -1):
            for j in range(budget, cost - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i - t][j - cost] + 1)
    
    return dp[time][budget]

3.4 示例

• 输入：maxAttractions([(5, 2), (10, 3), (15, 5)], 8, 20)
• 输出：3 （可以游览所有景点）

四、总结

动态规划是解决复杂问题的有效方法，通过将问题分解为更小的子问题，可以极大地提高算法的效率。在实际编程中，动态规划不仅仅是求解问题的手段，更是一种思维方式。希望通过这篇文章，你能对动态规划有更深入的理解，并在刷题过程中灵活应用。

---

以上就是关于动态规划的基本理论及其应用案例的分析。希望这篇文章能够帮助你在动态规划方面打下坚实的基础，并在后续的算法学习中取得更好的成绩！