动态规划 (Dynamic Programming)

概述

难度：困难 (Hard)
分类：Algorithm Paradigm / 算法思想

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

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

算法原理

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

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

复杂度分析

代码实现

# 以斐波那契为例
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

每日练习

1. 完成算法实现
2. 分析算法复杂度
3. 思考：算法的适用场景和局限性

相关阅读：算法专栏

💡 学习建议：算法学习重在理解思想，多写多练是关键。 💡 Learning tip: Algorithm learning is about understanding the core idea. Practice makes perfect.