🧮 动态规划 (Dynamic Programming)

难度 / Difficulty: 困难 (Hard)
分类 / Category: 算法思想 (Algorithm Paradigm)
时间复杂度 / Time Complexity: O(n)
空间复杂度 / Space Complexity: O(n) 或 O(1)

📖 算法简介 / Introduction

动态规划是一种将复杂问题分解为更小子问题的算法思想，通过存储子问题避免重复计算。

DP is an algorithm paradigm that decomposes complex problems into subproblems, storing results to avoid redundant computation.

💡 算法原理 / Principle

最优子结构 + 重叠子问题 = 动态规划。通过记忆化或自底向上避免重复计算。

Optimal substructure + overlapping subproblems = DP. Use memoization or bottom-up to avoid redundant computation.

📝 代码实现 / Implementation

# 以斐波那契为例
def fib_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# 空间优化版本
def fib_optimized(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

✨ 示例 / Example

计算斐波那契数列第10项：F(10) = 55。

Computing the 10th Fibonacci number: F(10) = 55.

🎯 适用场景 / Scenarios

最优路径问题, 资源分配, 字符串编辑距离

Optimal path problems, Resource allocation, String edit distance

🔄 扩展阅读 / Further Reading

• 建议在 LeetCode 或 HackerRank 上刷相关题目
• 尝试自己实现非递归版本
• 对比其他同类型算法的性能差异