#动态规划 #DP
Review
- 2024-10-09 07:10
[!Summary]
一、Introduction #
动态规划（Dynamic Programming，简称DP）是一种解决问题的方法，它通过把原问题分解为相对简单的子问题的方式求解复杂问题。这种方法特别适用于有重叠子问题和最优子结构性质的问题。
核心思想： #
- 分解问题： 将一个大问题分解成若干个子问题。
- 解决子问题： 从最小的子问题开始，逐个解决。
- 保存结果： 将子问题的解保存起来，避免重复计算。
- 合并结果： 利用子问题的解，逐步构建原问题的解。
两个关键性质： #
- 重叠子问题： 在求解过程中，会反复地求解相同的子问题。
- 最优子结构： 问题的最优解可以由其子问题的最优解得到。
动态规划的应用： #
- 最优化问题： 找出一个问题的最优解，如最长公共子序列、编辑距离等。
- 组合优化问题： 从多个方案中选择一个最优的方案，如背包问题、旅行商问题等。
- 博弈论问题： 分析博弈双方在不同情况下的决策，如Nim游戏等。
- 70. 爬楼梯 #Easy ✅ 2024-10-09
- 118. 杨辉三角 #Easy ✅ 2024-10-09
- 198. 打家劫舍 #Medium ✅ 2024-10-10