动态规划导论
- 定义：动态规划是一种算法技术，通过将复杂问题拆解成更简单的子问题并存储结果，以避免重复计算。
- 重叠子问题：在解决较大问题时，相同的小问题会多次出现。我们不再反复重新计算这些子问题，而是存储它们的解。
- 最优子结构：问题的最优解包含其子问题的最优解。这意味着我们可以通过将最佳方案组合到更小的部分来构建最佳解决方案。
动态规划解决方案
- Memoization（自上而下方法）：Memoization存储昂贵函数调用的结果，并在相同输入再次出现时返回缓存结果。
def climb_stairs_memo(n, memo={}): """Dynamic programming with memoization""" # Check if we've already calculated this value if n in memo: return memo[n] # Return cached result - O(1) lookup! # Base cases if n <= 2: return n # Calculate once and store in memo for future use memo[n] = climb_stairs_memo(n-1, memo) + climb_stairs_memo(n-2, memo) return memo[n]- 表格化（自下而上方法）：表格从零开始构建解决方案，在表格中填满子问题的解决方案。
def climb_stairs_tabulation(n): """Dynamic programming with tabulation""" if n <= 2: return n # Create array to store results for all steps from 0 to n dp = [0] * (n + 1) dp[1] = 1 # 1 way to reach step 1 dp[2] = 2 # 2 ways to reach step 2 # Build up the solution iteratively for i in range(3, n + 1): # Ways to reach step i = ways to reach (i-1) + ways to reach (i-2) dp[i] = dp[i-1] + dp[i-2] return dp[n]使用动态规划的现实应用
- 路线优化：GPS系统使用动态规划算法寻找地点之间的最短路径。
- 文本处理：拼写检查和自动补全功能通常依赖动态编程来计算单词之间的编辑距离。
- 财务建模：投资策略和投资组合优化经常采用动态规划技术。
- 资源分配：背包问题及其变体出现在调度、预算和资源管理中。
何时使用动态规划
你应该考虑在以下情景中使用动态规划：
- 问题可以拆解为重叠的子问题。
- 该问题表现出最优的子结构。
- 朴素递归解则需要反复计算。
- 你需要以牺牲空间复杂度为代价来优化时间复杂度。
