数据结构与算法（第二季）：动态规划

动态规划（Dynamic Programming）

一、概念

  • 动态规划，简称DP，是求解最优化问题的一种常见策略。

二、练习

322. 零钱兑换

image

image
  • 该实现属于暴力递归（自顶向下，出现了重叠子问题），优化方案是记忆化搜索（自顶向下）。
image
  • 我们还可以将记忆化搜索（自顶向下）继续优化，即递推（自底向上）。
image

  • 时间/空间复杂度为O(n)

  • 如果动态传入硬币面值：

image

三、动态规划的常规步骤

  • 动态规划中的“动态”，可以理解为是“会变化的状态”。

    1. 定义状态（状态是原问题、子问题的解），比如定义dp(i)的含义。
    2. 设置初始状态（边界），比如设置dp(0)的值。
    3. 确定状态转移方程，比如确定dp(i)和dp(i-1)的关系。

  • 动态规划就是将复杂的原问题，拆解成若干个简单子问题，并且每个子问题只计算一次，且存储他们的结果。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容