动态规划解题模板

发布于 2021-01-26 16:04:25   阅读量 48  点赞 0  

解题思路

 动态规划的一般形式是求最优解,其本质其实就是穷举法。但其目的在于缓存重叠子问题的解,用子问题的解来解决全局问题。

 动态规划的解题思路一般如下:

  • 找出问题的子结构

  • 列出正确的状态转移方程,而写出正确的状态转移方程一般需要明确以下几点:

    1. base case
    2. 子问题的状态
    3. 选择操作

 于是动态规划的解题模板可以总结为:

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1所有取值:
    for 状态2 in 状态2所有取值:
        for ...
            dp[状态1][状态2][...] = 求最值(选择1, 选择2, ...)


题型

 常见的动态规划问题类型有:


Last Modified : 2021-01-26 16:25:03