动态规划

技术文章 1年前 (2020) 完美者
1,172 0

标签:记录   框架   备忘   结果   计算   递增   大致   递归   空间   

动态规划是一个很好用的算法,同时也是令很多人头疼的算法,下面就介绍一下对动态规划的看法。
通过学习和刷题我们可以发现动态规划一般是用于求一些最值问题,比如说最长递增子序列等等,我们要想知道一个问题的最值,就要知道问题的所有答案然后通过比较得出答案,也就说我们平常所说的穷举;当然肯定不是暴力的穷举,对于一些动态规划的这类问题来说都是存在重叠子问题的,动态规划的做法是可以采用“备忘录”或者DP数组来避免不必要的计算。
动态规划的三要素是重叠子问题,最优子结构,状态转移方程;重叠子问题其实就是一些重新计算,比如我们之前计算过这个结果但是并没有保存,下次用到的时候需要重新计算,解决的方法可以是保存计算结果,下次用到的时候直接取用;最优子结构指的是问题的最优解包含子问题的最优解,也就是我们可以通过子问题的最优解推导出整个问题的最优解,要想有最右子结构,一般来说需要各个子问题之间是相互独立的;状态转移方程可以说是解决动态规划关键,当然也是挺困难的,大家可以通过多做题来感受一下,总结一下。
之前在学习的时候看到别人进行了相关的总结,觉得写得很好,在这里同样记录一下,以免忘记:总结了动态规划的一般步骤是 明确base case,明确【状态】,明确【选择】,定义dp数组/函数的含义;
并给出了一个一般的框架,如下所示:

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

其中确定base case比较简单,一般就是可以直接得到答案不用计算的情况;
确定【状态】,状态一般是原问题和子问题中会变化的变量;
确定【选择】,选择指的是会导致状态发生变化的行为,具体问题具体分析;
明确dp数组/函数的含义,一般来说定义dp函数是采用递归的方法,定义dp数组是采用递推的方式,递归是自顶向下的方法,一般函数的参数就是前文中的状态,dp数组一般是有几个状态就定义为几维的。
大致的动态规划就先介绍到这里,后面有经典的习题会及时补充,同时还有一个空间优化的问题。

动态规划

标签:记录   框架   备忘   结果   计算   递增   大致   递归   空间   

原文地址:https://www.cnblogs.com/noob-l/p/13619928.html

版权声明:完美者 发表于 2020-09-17 15:46:07。
转载请注明:动态规划 | 完美导航

暂无评论

暂无评论...