当前位置:   article > 正文

动态规划引入之记忆化搜索与递推_所有动态规划都可以用记忆化搜索吗

所有动态规划都可以用记忆化搜索吗

【前言】

在学习动态规划之前,我们必须要先掌握记忆化搜索和递推,这两块东西搞好了之后,面对动态规划那就容易多啦!

一、何为动态规划DP

动态规划(英语:Dynamic programming,简称 DP),通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 (是不是很像另外一种算法——分治,其实可以认为动态规划就是特殊的分治)

动态规划常常适用于有重叠子问题和最优子结构性质的问题,并且记录所有子问题的结果,因此动态规划方法所耗时间往往远少于暴力递归解法。

使用动态规划解决的问题有个明显的特点,一旦一个子问题的求解得到结果,以后的计算过程就不会修改它,这样的特点叫做无后效性,求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次,具有天然剪枝的功能,从而减少计算量

动态规划有自底向上自顶向下两种解决问题的方式。自顶向下即记忆化搜索,自底向上就是递推

好,那么本文主要讲解的记忆化搜索和递推也就浮出水面了,下面详细介绍(请放心,后面会详细讲解动态规划的,这部分既重要又很难,所以需要慢慢去理解。)

二、记忆化搜索

记忆化搜索的本质:动态规划。

记忆化搜索是动态规划的一种实现方式,记忆化搜索是用搜索的方式实现了动态规划,因此记忆化搜索就是动态规划。

提问:

何为记忆化搜索?

回答:

顾名思义,记忆化搜索肯定也就和“搜索”脱不了关系, 前面讲解的递归、DFS和BFS想必大家都已经掌握的差不多了,它们有个最大的弊病就是:低效!原因在于没有很好地处理重叠子问题。那么对于记忆化搜索呢,它虽然采用搜索的形式,但是它还有动态规划里面递推的思想,巧就巧在它将这两种方法很好的综合在了一起,简单又实用。

记忆化搜索,也叫记忆化递归,其实就是拆分子问题的时候,发现有很多重复子问题,然后再求解它们以后记录下来。以后再遇到要求解同样规模的子问题的时候,直接读取答案。

其实可以浅显的认为记忆化搜索就是简单DP,因为实在是太像了。 

下面详细讲解四道例题,让大家深入理解上面的概念:

典例1.斐波那契数列

题目描述:

  1. 示例1
  2. 输入:2
  3. 输出:1
  4. 解释:F(2) = F(1) + F(0) = 1 + 0 = 1
  5. 示例2
  6. 输入:3
  7. 输出:2
  8. 解释:F(3) = F(2) + F(1) = 1 + 1 = 2


方法一:暴力递归
代码执行:

  1. class Solution {
  2. public:
  3.     int fib(int n){
  4.         //方法一:暴力递归
  5.         //找边界
  6.         if(n == 0){
  7.             return 0;
  8.         }
  9.         if(n == 1){
  10.             return 1;
  11.         }
  12.         return fib(n - 1) + fib(n - 2);
  13.     }
  14. };


不用多说,学校老师讲递归的时候似乎都是拿这个举例。我们也知道这样写代码虽然简洁易懂,但是十分低效,低效在哪里?假设 n = 20,请画出递归树:

很显然,进行了大量的重复计算,虽然本题是一个很好的用来讲解递归的例子,但是嘞,本题在实际运用当中用递归来做那就太不明智啦,所以,这里就需要引入一个带有「备忘录」的递归,也就是前面所提到的记忆化搜索,下面看看具体怎么操作:

方法二:记忆化搜索
即然低效的原因是重复计算,那么我们可以造一个「备忘录」,每次算出某个子问题的答案后别急着返回,先记到「备忘录」里再返回;每次遇到一个子问题先去「备忘录」里查一查,如果发现之前已经解决过这个问题了,直接把答案拿出来用,不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」,当然你也可以使用哈希表(字典),思想都是一样的

这样去处理的话就无需进行重复计算了,相比前面的暴力递归就显得高效明智得多,而且很容易理解,不信你看:

代码执行:

  1. class Solution {
  2. public:
  3.     int fib(int n){
  4.         //方法三:记忆化搜索(简单DP)
  5.         //找边界
  6.         if(n == 0){
  7.             return 0;
  8.         }
  9.         if(n == 1){
  10.             return 1;
  11.         }
  12.         //需要定义一个大小为(n+1)的整形数组,并且初始化为0
  13.         //之所以是n+1,是因为要使用到n这个下标
  14.         vector<int> dp(n+1, 0);
  15.         dp[0] = 0;
  16.         dp[1] = 1;
  17.         for(int i = 2; i < n+1; i++)
  18.         {
  19.             dp[i] = dp[i - 1] + dp[i - 2];
  20.         }
  21.         return dp[n];
  22.     }
  23. };


当然也有这样的变形,多了一个要求,很简单的,大家看一下:

变形题


代码执行: 

  1. //找边界
  2.         if(n == 0)
  3.             return 0;
  4.         if(n == 1)
  5.             return 1;
  6.         vector<int> dp(n + 1, 0);//开辟一个大小为n+1的整形数组(因为需要使用下标n),并且初始化为0
  7.         dp[0] = 0;
  8.         dp[1] = 1;
  9.         for(int i = 2; i < n+1; i++)
  10.         {
  11.             dp[i] = dp[i - 1] + dp[i - 2];
  12.             dp[i] = dp[i] % 1000000007;
  13.         }
  14.         return dp[n];
  15.     }


实际上,这种解法和迭代的动态规划非常相似,只不过这种方法叫做「自顶向下」,动态规划叫做「自底向上」

啥叫「自顶向下」?

注意我们刚才画的递归树(或者说图),是从上向下延伸,都是从一个规模较大的原问题比如说 f(20),向下逐渐分解,直至 f(1) 和 f(2) 这两个 base case,然后逐层返回答案,这就叫「自顶向下」。

啥叫「自底向上」?

反过来,我们直接从最底下,最简单,问题规模最小的 f(1) 和 f(2) 开始往上推,直到推到我们想要的答案 f(20),这就是动态规划的思路,这也是为什么动态规划一般都脱离了递归,而是由循环迭代完成计算。

典例2:爬楼梯(青蛙跳台阶)

题目描述:

  1. 示例1
  2. 输入: 2
  3. 输出: 2
  4. 解释: 有两种方法可以爬到楼顶。
  5. 1.  1+ 1
  6. 2.  2
  7. 示例2
  8. 输入: 3
  9. 输出: 3
  10. 解释: 有三种方法可以爬到楼顶。
  11. 1.  1+ 1+ 1
  12. 2.  1+ 2
  13. 3.  2+ 1


首先分析一下本题:

注意:这个题目问的是什么?

问的不是能爬多少次,而是有多少种方法能到最后一个台阶。

问题分析:

当n > 2时,第一次爬就有两种不同的选择:一是第一次只爬一级,此时爬法数目等于后面剩下的(n - 1)级台阶的爬法数目,即为f(n - 1); 还有一种选择是第一次爬两级,此时爬法数目等于后面剩下的(n - 2)级台阶的爬法数目,即为f(n - 2).

所以有:f(n) = f(n - 1) + f(n - 2)

当n == 1时,有1种爬法;

当n == 2时,有2种爬法;

当n == 3时,有3种爬法;

当n == 4时,有5种爬法。

是呀,这题跟斐波那契数列基本上一样,不过这道题目需要思考一下,没有斐波那契数列这么明显。但是需要注意的是,递归边界还是有所不同的哦!

方法一:暴力递归 
代码执行:

  1. class Solution {
  2. public:
  3.     int climbStairs(int n) {
  4.         //方法一:暴力递归
  5.         //找边界
  6.         if(n == 1){
  7.             return 1;
  8.         }
  9.         if(n == 2){
  10.             return 2;
  11.         }
  12.         return climbStairs(n - 1) + climbStairs(n - 2);
  13.     }
  14. };


方法二:记忆化搜索
代码执行:

  1. class Solution {
  2. public:
  3.     int climbStairs(int n) {
  4.         //方法二:记忆化搜索(简单DP)
  5.         //找边界
  6.         if(n == 1){
  7.             return 1;
  8.         }
  9.         if(n == 2){
  10.             return 2;
  11.         }
  12.         //定义一个大小为n+1的整型数组,并且初始化为0
  13.         vector<int> dp(n+1, 0);
  14.         dp[1] = 1;
  15.         dp[2] = 2;
  16.         for(int i = 3; i < n+1; i++)
  17.         {
  18.             dp[i] = dp[i - 1] + dp[i - 2];
  19.         }
  20.         return dp[n];
  21.     }
  22. };


变形题 
其实就是多了一个要求...

代码执行:

  1. class Solution {
  2. public:
  3.     int numWays(int n) {
  4.         //找边界
  5.         if(n == 0 || n == 1)
  6.             return 1;
  7.         if(n == 2)
  8.             return 2;
  9.         vector<int> dp(n+1, 0);
  10.         dp[1] = 1;
  11.         dp[2] = 2;
  12.         for(int i = 3; i < n+1; i++)
  13.         {
  14.             dp[i] = dp[i - 1] + dp[i - 2];
  15.             dp[i] %= 1000000007;
  16.         }
  17.         return dp[n];
  18.     }
  19. };


典例3.第N个泰波那契数

题目描述: 

  1. 示例1
  2. 输入:n = 4
  3. 输出:4
  4. 解释:
  5. T_3 = 0 + 1 + 1 = 2
  6. T_4 = 1 + 1 + 2 = 4
  7. 示例2
  8. 输入:n = 25
  9. 输出:1389537


代码执行:

  1. class Solution {
  2. public:
  3.     int tribonacci(int n) {
  4.         //找边界
  5.         if(n == 0)
  6.             return 0;
  7.         if(n == 1 || n == 2)
  8.             return 1;
  9.         //定义一个大小为n+1的整形数组,并将其初始为0
  10.         vector<int> dp(n+1, 0);
  11.         dp[0] = 0;
  12.         dp[1] = 1;
  13.         dp[2] = 1;
  14.         for(int i = 3; i < n+1;i++)
  15.         {
  16.             dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];//递推公式
  17.         }
  18.         return dp[n];
  19.     }
  20.  
  21. };


上面这三道题是非常简单的,理解了上面的题目,下面这道题肯定就会非常容易了。

典例4.Function

题目描述:

输入格式:

输入有若干行。并以−1,−1,−1结束。

保证输入的数在[−9223372036854775808,9223372036854775807]之间,并且是整数。

输出格式

输出若干行,每一行格式:w(a, b, c) = ans

思路:

本题重在理解题意,题目不难,但是要把题目多读几遍。 

代码执行:

  1. #include <stdio.h>
  2.  
  3. #define LL long long
  4.  
  5. LL dp[25][25][25];
  6.  
  7. LL w(LL a, LL b, LL c)
  8. {
  9.     //两个特殊情况判断
  10.     if(a <= 0 || b <= 0 || c <= 0
  11.         return 1;
  12.     if(a > 20 || b > 20 || c > 20
  13.         return w(20, 20, 20);
  14.     
  15.     if(a < b && b < c)
  16.     {
  17.         if(dp[a][b][c-1] == 0)
  18.         {
  19.             dp[a][b][c-1] = w(a, b, c-1);
  20.         }
  21.         if(dp[a][b-1][c-1] == 0)
  22.         {
  23.             dp[a][b-1][c-1] = w(a, b-1 ,c-1);
  24.         }
  25.         if(dp[a][b-1][c] == 0)
  26.         {
  27.             dp[a][b-1][c] = w(a, b-1, c);
  28.         }
  29.         dp[a][b][c] = dp[a][b][c-1] + dp[a][b-1][c-1] - dp[a][b-1][c];
  30.     }
  31.     else
  32.     {
  33.         if(dp[a-1][b][c] == 0)
  34.         {
  35.             dp[a-1][b][c] = w(a-1, b, c);
  36.         }
  37.         if(dp[a-1][b-1][c] == 0)
  38.         {
  39.             dp[a-1][b-1][c] = w(a-1, b-1 ,c);
  40.         }
  41.         if(dp[a-1][b][c-1] == 0)
  42.         {
  43.             dp[a-1][b][c-1] = w(a-1, b, c-1);
  44.         }
  45.         if(dp[a-1][b-1][c-1] == 0)
  46.         {
  47.             dp[a-1][b-1][c-1] = w(a-1, b-1, c-1);
  48.         }
  49.         dp[a][b][c] = dp[a-1][b][c] + dp[a-1][b][c-1] + dp[a-1][b-1][c] - dp[a-1][b-1][c-1];
  50.     }
  51.     
  52.     return dp[a][b][c];
  53. }
  54.  
  55. int main()
  56. {
  57.     LL a, b, c;
  58.     
  59.     while(scanf("%lld%lld%lld", &a, &b, &c) != EOF)
  60.     {
  61.         if(a == -1 && b == -1 && c == -1
  62.             return 0;//当输入的值为-1 -1 -1时直接结束循环
  63.         
  64.         printf("w(%lld, %lld, %lld) = ", a, b, c);
  65.         printf("%lld\n", w(a, b, c));
  66.     }
  67. }

三、递推

看到“递推”,大家肯定能联想到“递归”,好嘞,接下来向大家详细讲解递推和递归有哪些区别。

递归是大问题转化为小问题,不断调用自身或不断被间接调用的一类算法。

1.递归算法的关键是要找出大问题和小问题的联系----即找重复,进而使大问题的规模不断减小,直至可以被直接解决。

2.递归算法的另一个关键点是终止条件----即找边界,这个是十分重要的。

有时,递归算法的效率会很低,这时候就可以用上面所说的记忆化搜索,即建立一个数组,用来记录每次递归得到的答案,这样如果后面要继续使用这个值的时候,就不用再次计算了,也就避免了重复计算问题。

 

2.递推

递推和递归非常相似。

递推是把问题划分为若干个步骤,每个步骤之间,或者是这个步骤与之前的几个步骤之间有一定的数量关系,可以用前几项的值表示出这一项的值,这样就可以把一个复杂的问题变成很多小的问题。

递推算法注意的是设置什么样的递推状态,因为一个好的递推状态可以让问题很简单。最难的是想出递推公式,一般递推公式是从后面向前想,倒推回去。

典例5.骨牌问题

题目描述:

有 2*n的一个长方形方格,用一个1*2的骨牌铺满方格。请编写一个程序,试对给出的任意一个n(n>0), 输出铺法总数。 

思路:

其实这道题目很简单的,找到递推公式即可,跟上面的爬楼梯问题很相似,这里就详细分析一下:

n = 1 时,只有一种铺法
n = 2 时,如下图,有全部竖着铺和横着铺两种
n = 3 时,骨牌可以全部竖着铺,也可以认为在方格中已经有一个竖铺的骨牌,则需要在方格中排列两个横排骨牌(无重复方法),若已经在方格中排列两个横排骨牌,则必须在方格中排列一个竖排骨牌。如下图,再无其他排列方法,因此铺法总数表示为三种。
通过上面的分析,不难看出规律:f(3) = f(1) + f(2)

所以可以的得到递推关系:f(n) = f(n - 1) + f(n - 2)

 

  1. class Solution {
  2. public:
  3. int brand(int n) {
  4. //找边界
  5. if(n == 1){
  6. return 1;
  7. }
  8. if(n == 2){
  9. return 2;
  10. }
  11. //定义一个大小为n+1的整型数组,并且初始化为0
  12. vector<int> dp(n+1, 0);
  13. dp[1] = 1;
  14. dp[2] = 2;
  15. for(int i = 3; i < n+1; i++)
  16. {
  17. dp[i] = dp[i - 1] + dp[i - 2];//找出递推关系
  18. }
  19. return dp[n];
  20. }
  21. };

典例6.杨辉三角

  1. 示例1
  2. 输入: numRows = 5
  3. 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
  4. 示例2
  5. 输入: numRows = 1
  6. 输出: [[1]]

思路:

本题比较简单,很容易就能看出递推关系,从第三行第二列开始,每个数是它左上方和右上方的数的和。 

  1. class Solution {
  2. public:
  3. vector<vector<int>> generate(int numRows) {
  4. vector<vector<int> >ret(numRows);//定义一个二维数组用于存放结果
  5. //首先将第一列和最后一列元素全部赋值为1
  6. for(int i = 0; i < numRows; i++)
  7. {
  8. ret[i].resize(i+1);//resize()的作用就是为一维数组分配空间
  9. ret[i][0] = ret[i][i] = 1;
  10. //从第三行第二列开始有递推关系:ret[i][j] = ret[i+1][j]+ret[i+1][j+1];
  11. for(int j = 1; j < i; j++)
  12. {
  13. ret[i][j] = ret[i-1][j] + ret[i-1][j-1];
  14. }
  15. }
  16. return ret;
  17. }
  18. };

典例7.数字三角形

输入格式:

第一个行一个正整数 n ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式:

单独的一行,包含那个可能得到的最大的和。

数据范围:

1 ≤ n ≤ 1000,三角形数字值在 [0,100] 范围内。 

示例:

输入:

  1. 输入:
  2. 5
  3. 7
  4. 3 8
  5. 8 1 0
  6. 2 7 4 4
  7. 4 5 2 6 5
  8. 输出:
  9. 30

思路:

本题采用倒推的方式:

假设func[i][j]表示的是从 i, j 到最后一层的最大路径之和

当从顶层沿某条路径走到第i层向第i+1层前进时,我们的选择是沿其下两条可行路径中最大数字的方向前进,所以找出递推关系:func[i][j] += max(func[i+1][j],func[i+1][j+1]);
注意:func[i][j]表示当前数字的值,func[i+1][j]和func[i+1][j+1]分别表示从i+1,j、i+1,j+1到最后一层的最大路径之和;
最终func[0][0]就是所求

 

  1. #include<stdio.h>
  2. #include<algorithm>
  3. using namespace std;
  4. int func[1005][1005] = {0};
  5. int main()
  6. {
  7. int n = 0;
  8. scanf("%d", &n);
  9. int i = 0;
  10. int j = 0;
  11. for(i = 0; i < n; i++)
  12. {
  13. for(j = 0; j <= i; j++)
  14. {
  15. scanf("%d", &func[i][j]);
  16. }
  17. }
  18. //假设func[i][j]表示的是从i, j到最后一层的最大路径之和
  19. //找出递推关系:func[i][j]+=max(func[i+1][j],func[i+1][j+1]);
  20. //func[i][j]表示当前数字的值,func[i+1][j]和func[i+1][j+1]分别表示从i+1,j、i+1,j+1到最后一层的最大路径之和
  21. //最终func[0][0]就是所求
  22. for(i = n - 2; i >= 0; i--)
  23. {
  24. for(j = 0; j <= i; j++)
  25. {
  26. func[i][j] += max(func[i+1][j], func[i+1][j+1]);
  27. }
  28. }
  29. printf("%d\n", func[0][0]);
  30. return 0;
  31. }

以上内容转载自【蓝桥杯】最难算法没有之一· 动态规划真的这么好理解?(引入)_安然无虞的博客-CSDN博客_最难算法

 

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号