什么是动态规划
动态规划(DP, Dynamic Programming)
一句话总结:在求解一个复杂问题时,将其分解为若干个简单问题。通过求解简单问题的最优解,来找到目标问题的最优解。
动态规划能做什么
常见问题
- 求解斐波那契数列第 N 项 (Leetcode 509. Fibonacci Number)
- 背包问题
- 阶梯问题 (Leetcode 70. Climbing Stairs)
- 硬币问题 (Leetcode 322. Coin Change)
怎么求解动态规划问题
我们通过一个例子来了解一下DP的基本原理。
首先,我们要找到某个状态的最优解,然后在它的帮助下,找到下一个状态的最优解。
如硬币问题的例子
硬币问题:如果我们有面值为1元、3元和5元的硬币若干枚,如何用最少的硬币凑够11元?