写点什么

理论 + 实践,带你掌握动态规划法

  • 2022 年 2 月 28 日
  • 本文字数:3045 字

    阅读完需:约 10 分钟

摘要:本文介绍了动态规划法的基本概念,通过详细解析动态规划法的特征,给出判断问题是否使用动态规划法结题的思路。


本文分享自华为云社区《五大基础算法--动态规划法》,作者: 大金(内蒙的)。

一、基本概念

动态规划法,和分治法极其相似。区别就是,在求解子问题时,会保存该子问题的解,后面的子问题求解时,可以直接拿来计算。

专业的说法是:

对于一个规模为 n 的问题,将其分解为 k 个规模较小的子问题(阶段),按顺序求解子问题,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,通过决策求得局部最优解,依次解决各子问题。最后可以通过简单的判断,得到原问题的解。

说法有些晦涩难懂,我给大家解释下:

阶段:求解第 n 个子问题称为第 n 个阶段。动态规划是按照顺序去求解子问题的,这里子问题的求解顺序很重要。状态:在求解第 n 个阶段时,已求解 n-1 个阶段的解,称为状态。决策:在求解第 n 个阶段时,根据状态和计算规则,可以得到第 n 个阶段时解。

二、基本特征

动态规划法所能解决的问题一般具有以下几个特征:

1) 大问题可分解性

该问题可以分解为若干个规模较小的问题,即该问题具有最优子结构性质。

2) 子问题易解决性

该问题的规模缩小到一定的程度就可以容易地解决

3) 解可合并性

利用该问题分解出的子问题的解可以合并为该问题的解;

4) 子问题重叠性

当计算出某个子问题的解时,后续多个问题都需要计算该子问题的解,所以在计算某个子问题的解,将其保存,就节省了分治法重复计算的时间。

三、一些误解

1.状态转移方程

很多博客都说什么状态转移方程,感觉说的很高大上,一般解题上来就是状态转移方程是 xxxx,代码是 xxxx,翻译下是什么意思呢?在求解第 n 个子问题的时候,通过已求解 n-1 个阶段的解和计算规则,可以得到第 n 个阶段时解。即是最新的状态=目前的状态+决策。

2.初始化

很多题目解题的时候都说初始化,这并不是动态规划法的步骤。应该正确的去理解这些操作。动态规划在划分子问题求解顺序时,基本是先求解易求解最小的子问题,在由这些已经求解的阶段+计算规则,就能直接求得第 n 阶段的解。所以初始化的含义是,求得初始阶段的解。

3.边界条件

一般题目会说边界是啥,可以理解为怎么判断所有的子问题已经求解结束了。正常人也不会写 while(true)吧,你总得让程序结束,判断你已经解决好这个问题了。

四、动态规划法的基本步骤

step1 分解:

将一个问题分解为多个子问题,需要注意子问题解决的顺序,应该先求解易求解的子问题,且后续的阶段可以通过前面的阶段+决策得到。

step2 状态转移:

通过得到的规律,写出状态转移方程。第 n 阶段=当前状态+决策(前 n 个阶段解和计算规则)

step3 写代码:

将最先算的阶段计算出来,中间阶段通过状态转移方程计算状态,直到所有阶段计算结束。

step4 得到解:

所有阶段计算结束,可以通过简单的统计,例如 Max,Min 等遍历阶段的值,得到最后的解。

五、经典问题

好记性不如烂笔头,有一些适用动态规划法的问题,可以帮我们不断强化的解题思想。在解决问题时,希望大家可以注意判断题目的解决思路,看是否符合动态规划法的四个特征,这样不断强化,才能将算法掌握。

最长回文子串

下面附上我的题解:

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/dong-tai-gui-hua-fa-qiu-jie-kan-bu-dong-octkt/

//动态规划法两个基本要素:最优子结构性质和子问题重叠性质。//很多答案写了初始化和边界条件,个人认为你要分清楚他的目的是什么。//很多初始化和边界条件,是因为状态转移方程,是需要初始化的子问题的解,从而避免重复计算,说白了还是子问题重叠和最优子结构问题。//我们应该注重某一个问题的重叠子问题分解和状态最优的决策分析。//解题思路://计算某个字符串时, 如果它首尾字符相等,则它是不是回文,取决于去掉头尾之后的字符串是否为回文串。//                  如果它首尾字符不相等,则它一定不是回文//leetcode submit region begin(Prohibit modification and deletion)class Solution {    public String longestPalindrome(String s) {        int len = s.length();        // 特判        if (len < 2){            return s;        }
int maxLen = 1; int begin = 0;
// 1. 状态定义 // dp[i][j] 表示s[i...j] 是否是回文串,现在表示全部为0,不是回文串 boolean[][] dp = new boolean[len][len]; char[] chars = s.toCharArray(); // 2. 子问题计算顺序:先计算短字符串,在计算长字符串,同时根据已求得的短字符串或者计算规则,可以得到长字符串的解。
// 注意:s表示计算的元素顺序。 // 0 1 2 3 4 // 0 xx s1 s2 s4 s7 // 1 xx s3 s5 s8 // 2 xx s6 s9 // 3 xx s10 // 4 xx // 为什么这么写呢,因为你要保证保证计算某个元素时,通过状态转移方程能得到左上角元素的dp[][]。 // 填表规则:先一列一列的填写,再一行一行的填,保证计算某个元素时,它左上方的单元格已经被计算出了结果 // 填表规则:当然你也可以由左往右一行一行写,这样也能保证计算某个元素时,它左上方的单元格已经被计算出了结果 for (int j = 1;j < len;j++){ for (int i = 0; i < j; i++) { // 头尾字符不相等,不是回文串 if (chars[i] != chars[j]){ dp[i][j] = false; }else { // 相等的情况下 // 因为考虑头尾去掉以后没有字符剩余,或者剩下一个字符的时候,肯定是回文串 if (j - i -1 <= 1){ dp[i][j] = true; }else { // 头尾相等,中间有大于1个元素,这个时候,我们无法直接判断他是不是回文,但是我们可以通过状态转移方程去判断
// 其实这个就是在计算s8这个元素时,我们无法判断dp[1][4]在1和4位元素相等时候,整个字符串是否是回文。 // 所以要通过s4去判断,s4是回文,s8就是。s4不是,那s8就不是。 dp[i][j] = dp[i + 1][j - 1]; } }
// 只要dp[i][j] == true 成立,表示s[i...j] 是否是回文串 // 此时更新记录回文长度和起始位置 if (dp[i][j] && (j - i + 1 > maxLen)){ maxLen = j - i + 1; begin = i; } } }
// 3. 初始化 // 很多答案写了这个,这一步,我们细想,其实完全没有必要。 // 因为主对角线,值是可以直接判断出来的。 // 而且在求解过程中,我们的状态转移方程不会用到这个值。因为只有主对角线会用到这几个值。 // 而且单个元素的子问题解,我们并不需要。 // 所以,即使我这步初始化放到计算之后,甚至是直接去掉,也完全不影响结果。大家可以自己试一下 // for (int i = 0; i < len; i++) { // dp[i][i] = true; // } // 4. 返回值 return s.substring(begin,begin + maxLen); }}
复制代码


点击关注,第一时间了解华为云新鲜技术~

发布于: 刚刚阅读数: 3
用户头像

提供全面深入的云计算技术干货 2020.07.14 加入

华为云开发者社区,提供全面深入的云计算前景分析、丰富的技术干货、程序样例,分享华为云前沿资讯动态,方便开发者快速成长与发展,欢迎提问、互动,多方位了解云计算! 传送门:https://bbs.huaweicloud.com/

评论

发布
暂无评论
理论+实践,带你掌握动态规划法