动态规划（Dynamic Programming）
一、概念
- 动态规划，简称DP，是求解最优化问题的一种常见策略。
二、练习
image
image
- 该实现属于
暴力递归（自顶向下，出现了重叠子问题），优化方案是记忆化搜索（自顶向下）。
image
- 我们还可以将
记忆化搜索（自顶向下）继续优化，即递推（自底向上）。
image
-
时间/空间复杂度为
O(n) -
如果动态传入硬币面值：
image
三、动态规划的常规步骤
-
动态规划中的“动态”，可以理解为是“会变化的状态”。
- 定义状态（状态是原问题、子问题的解），比如定义dp(i)的含义。
- 设置初始状态（边界），比如设置dp(0)的值。
- 确定状态转移方程，比如确定dp(i)和dp(i-1)的关系。
-
动态规划就是将复杂的原问题，拆解成若干个简单子问题，并且每个子问题只计算一次，且存储他们的结果。
网友评论