赞
踩
【前言】
动态规划(英语:Dynamic programming,简称 DP),通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 (是不是很像另外一种算法——分治,其实可以认为动态规划就是特殊的分治)
动态规划常常适用于有重叠子问题和最优子结构性质的问题,并且记录所有子问题的结果,因此动态规划方法所耗时间往往远少于暴力递归解法。
使用动态规划解决的问题有个明显的特点,一旦一个子问题的求解得到结果,以后的计算过程就不会修改它,这样的特点叫做无后效性,求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次,具有天然剪枝的功能,从而减少计算量。
动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化搜索,自底向上就是递推。
好,那么本文主要讲解的记忆化搜索和递推也就浮出水面了,下面详细介绍(请放心,后面会详细讲解动态规划的,这部分既重要又很难,所以需要慢慢去理解。)
记忆化搜索的本质:动态规划。
记忆化搜索是动态规划的一种实现方式,记忆化搜索是用搜索的方式实现了动态规划,因此记忆化搜索就是动态规划。
提问:
何为记忆化搜索?
回答:
顾名思义,记忆化搜索肯定也就和“搜索”脱不了关系, 前面讲解的递归、DFS和BFS想必大家都已经掌握的差不多了,它们有个最大的弊病就是:低效!原因在于没有很好地处理重叠子问题。那么对于记忆化搜索呢,它虽然采用搜索的形式,但是它还有动态规划里面递推的思想,巧就巧在它将这两种方法很好的综合在了一起,简单又实用。
记忆化搜索,也叫记忆化递归,其实就是拆分子问题的时候,发现有很多重复子问题,然后再求解它们以后记录下来。以后再遇到要求解同样规模的子问题的时候,直接读取答案。
其实可以浅显的认为记忆化搜索就是简单DP,因为实在是太像了。
下面详细讲解四道例题,让大家深入理解上面的概念:
题目描述:
- 示例1:
-
- 输入:2
- 输出:1
- 解释:F(2) = F(1) + F(0) = 1 + 0 = 1
- 示例2:
-
- 输入:3
- 输出:2
- 解释:F(3) = F(2) + F(1) = 1 + 1 = 2
方法一:暴力递归
代码执行:
- class Solution {
- public:
- int fib(int n){
- //方法一:暴力递归
- //找边界
- if(n == 0){
- return 0;
- }
- if(n == 1){
- return 1;
- }
- return fib(n - 1) + fib(n - 2);
- }
- };
不用多说,学校老师讲递归的时候似乎都是拿这个举例。我们也知道这样写代码虽然简洁易懂,但是十分低效,低效在哪里?假设 n = 20,请画出递归树:
很显然,进行了大量的重复计算,虽然本题是一个很好的用来讲解递归的例子,但是嘞,本题在实际运用当中用递归来做那就太不明智啦,所以,这里就需要引入一个带有「备忘录」的递归,也就是前面所提到的记忆化搜索,下面看看具体怎么操作:
方法二:记忆化搜索
即然低效的原因是重复计算,那么我们可以造一个「备忘录」,每次算出某个子问题的答案后别急着返回,先记到「备忘录」里再返回;每次遇到一个子问题先去「备忘录」里查一查,如果发现之前已经解决过这个问题了,直接把答案拿出来用,不要再耗时去计算了。一般使用一个数组充当这个「备忘录」,当然你也可以使用哈希表(字典),思想都是一样的。
这样去处理的话就无需进行重复计算了,相比前面的暴力递归就显得高效明智得多,而且很容易理解,不信你看:
代码执行:
- class Solution {
- public:
- int fib(int n){
- //方法三:记忆化搜索(简单DP)
- //找边界
- if(n == 0){
- return 0;
- }
- if(n == 1){
- return 1;
- }
- //需要定义一个大小为(n+1)的整形数组,并且初始化为0
- //之所以是n+1,是因为要使用到n这个下标
- vector<int> dp(n+1, 0);
- dp[0] = 0;
- dp[1] = 1;
- for(int i = 2; i < n+1; i++)
- {
- dp[i] = dp[i - 1] + dp[i - 2];
- }
- return dp[n];
- }
- };
当然也有这样的变形,多了一个要求,很简单的,大家看一下:
变形题
代码执行:
- //找边界
- if(n == 0)
- return 0;
- if(n == 1)
- return 1;
- vector<int> dp(n + 1, 0);//开辟一个大小为n+1的整形数组(因为需要使用下标n),并且初始化为0
- dp[0] = 0;
- dp[1] = 1;
- for(int i = 2; i < n+1; i++)
- {
- dp[i] = dp[i - 1] + dp[i - 2];
- dp[i] = dp[i] % 1000000007;
- }
- return dp[n];
- }
实际上,这种解法和迭代的动态规划非常相似,只不过这种方法叫做「自顶向下」,动态规划叫做「自底向上」。
啥叫「自顶向下」?
注意我们刚才画的递归树(或者说图),是从上向下延伸,都是从一个规模较大的原问题比如说 f(20),向下逐渐分解,直至 f(1) 和 f(2) 这两个 base case,然后逐层返回答案,这就叫「自顶向下」。
啥叫「自底向上」?
反过来,我们直接从最底下,最简单,问题规模最小的 f(1) 和 f(2) 开始往上推,直到推到我们想要的答案 f(20),这就是动态规划的思路,这也是为什么动态规划一般都脱离了递归,而是由循环迭代完成计算。
典例2:爬楼梯(青蛙跳台阶)
题目描述:
- 示例1:
-
- 输入: 2
- 输出: 2
- 解释: 有两种方法可以爬到楼顶。
- 1. 1 阶 + 1 阶
- 2. 2 阶
- 示例2:
-
- 输入: 3
- 输出: 3
- 解释: 有三种方法可以爬到楼顶。
- 1. 1 阶 + 1 阶 + 1 阶
- 2. 1 阶 + 2 阶
- 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种爬法。
是呀,这题跟斐波那契数列基本上一样,不过这道题目需要思考一下,没有斐波那契数列这么明显。但是需要注意的是,递归边界还是有所不同的哦!
方法一:暴力递归
代码执行:
- class Solution {
- public:
- int climbStairs(int n) {
- //方法一:暴力递归
- //找边界
- if(n == 1){
- return 1;
- }
- if(n == 2){
- return 2;
- }
- return climbStairs(n - 1) + climbStairs(n - 2);
- }
- };
方法二:记忆化搜索
代码执行:
- class Solution {
- public:
- int climbStairs(int n) {
- //方法二:记忆化搜索(简单DP)
- //找边界
- if(n == 1){
- return 1;
- }
- if(n == 2){
- return 2;
- }
- //定义一个大小为n+1的整型数组,并且初始化为0
- vector<int> dp(n+1, 0);
- dp[1] = 1;
- dp[2] = 2;
- for(int i = 3; i < n+1; i++)
- {
- dp[i] = dp[i - 1] + dp[i - 2];
- }
- return dp[n];
- }
- };
变形题
其实就是多了一个要求...
代码执行:
- class Solution {
- public:
- int numWays(int n) {
- //找边界
- if(n == 0 || n == 1)
- return 1;
- if(n == 2)
- return 2;
- vector<int> dp(n+1, 0);
- dp[1] = 1;
- dp[2] = 2;
- for(int i = 3; i < n+1; i++)
- {
- dp[i] = dp[i - 1] + dp[i - 2];
- dp[i] %= 1000000007;
- }
- return dp[n];
- }
- };
典例3.第N个泰波那契数
题目描述:
- 示例1:
-
- 输入:n = 4
- 输出:4
- 解释:
- T_3 = 0 + 1 + 1 = 2
- T_4 = 1 + 1 + 2 = 4
- 示例2:
-
- 输入:n = 25
- 输出:1389537
代码执行:
- class Solution {
- public:
- int tribonacci(int n) {
- //找边界
- if(n == 0)
- return 0;
- if(n == 1 || n == 2)
- return 1;
- //定义一个大小为n+1的整形数组,并将其初始为0
- vector<int> dp(n+1, 0);
- dp[0] = 0;
- dp[1] = 1;
- dp[2] = 1;
- for(int i = 3; i < n+1;i++)
- {
- dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];//递推公式
- }
- return dp[n];
- }
-
- };
上面这三道题是非常简单的,理解了上面的题目,下面这道题肯定就会非常容易了。
典例4.Function
题目描述:
输入格式:
输入有若干行。并以−1,−1,−1结束。
保证输入的数在[−9223372036854775808,9223372036854775807]之间,并且是整数。
输出格式
输出若干行,每一行格式:w(a, b, c) = ans
思路:
本题重在理解题意,题目不难,但是要把题目多读几遍。
代码执行:
- #include <stdio.h>
-
- #define LL long long
-
- LL dp[25][25][25];
-
- LL w(LL a, LL b, LL c)
- {
- //两个特殊情况判断
- if(a <= 0 || b <= 0 || c <= 0)
- return 1;
- if(a > 20 || b > 20 || c > 20)
- return w(20, 20, 20);
-
- if(a < b && b < c)
- {
- if(dp[a][b][c-1] == 0)
- {
- dp[a][b][c-1] = w(a, b, c-1);
- }
- if(dp[a][b-1][c-1] == 0)
- {
- dp[a][b-1][c-1] = w(a, b-1 ,c-1);
- }
- if(dp[a][b-1][c] == 0)
- {
- dp[a][b-1][c] = w(a, b-1, c);
- }
- dp[a][b][c] = dp[a][b][c-1] + dp[a][b-1][c-1] - dp[a][b-1][c];
- }
- else
- {
- if(dp[a-1][b][c] == 0)
- {
- dp[a-1][b][c] = w(a-1, b, c);
- }
- if(dp[a-1][b-1][c] == 0)
- {
- dp[a-1][b-1][c] = w(a-1, b-1 ,c);
- }
- if(dp[a-1][b][c-1] == 0)
- {
- dp[a-1][b][c-1] = w(a-1, b, c-1);
- }
- if(dp[a-1][b-1][c-1] == 0)
- {
- dp[a-1][b-1][c-1] = w(a-1, b-1, c-1);
- }
- 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];
- }
-
- return dp[a][b][c];
- }
-
- int main()
- {
- LL a, b, c;
-
- while(scanf("%lld%lld%lld", &a, &b, &c) != EOF)
- {
- if(a == -1 && b == -1 && c == -1)
- return 0;//当输入的值为-1 -1 -1时直接结束循环
-
- printf("w(%lld, %lld, %lld) = ", a, b, c);
- printf("%lld\n", w(a, b, c));
- }
- }
看到“递推”,大家肯定能联想到“递归”,好嘞,接下来向大家详细讲解递推和递归有哪些区别。
递归是大问题转化为小问题,不断调用自身或不断被间接调用的一类算法。
1.递归算法的关键是要找出大问题和小问题的联系----即找重复,进而使大问题的规模不断减小,直至可以被直接解决。
2.递归算法的另一个关键点是终止条件----即找边界,这个是十分重要的。
有时,递归算法的效率会很低,这时候就可以用上面所说的记忆化搜索,即建立一个数组,用来记录每次递归得到的答案,这样如果后面要继续使用这个值的时候,就不用再次计算了,也就避免了重复计算问题。
递推和递归非常相似。
递推是把问题划分为若干个步骤,每个步骤之间,或者是这个步骤与之前的几个步骤之间有一定的数量关系,可以用前几项的值表示出这一项的值,这样就可以把一个复杂的问题变成很多小的问题。
递推算法注意的是设置什么样的递推状态,因为一个好的递推状态可以让问题很简单。最难的是想出递推公式,一般递推公式是从后面向前想,倒推回去。
题目描述:
有 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)
- class Solution {
- public:
- int brand(int n) {
-
- //找边界
- if(n == 1){
- return 1;
- }
- if(n == 2){
- return 2;
- }
- //定义一个大小为n+1的整型数组,并且初始化为0
- vector<int> dp(n+1, 0);
- dp[1] = 1;
- dp[2] = 2;
- for(int i = 3; i < n+1; i++)
- {
- dp[i] = dp[i - 1] + dp[i - 2];//找出递推关系
- }
- return dp[n];
- }
- };
- 示例1:
-
- 输入: numRows = 5
- 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
- 示例2:
-
- 输入: numRows = 1
- 输出: [[1]]
思路:
本题比较简单,很容易就能看出递推关系,从第三行第二列开始,每个数是它左上方和右上方的数的和。
- class Solution {
- public:
- vector<vector<int>> generate(int numRows) {
- vector<vector<int> >ret(numRows);//定义一个二维数组用于存放结果
- //首先将第一列和最后一列元素全部赋值为1
- for(int i = 0; i < numRows; i++)
- {
- ret[i].resize(i+1);//resize()的作用就是为一维数组分配空间
- ret[i][0] = ret[i][i] = 1;
- //从第三行第二列开始有递推关系:ret[i][j] = ret[i+1][j]+ret[i+1][j+1];
- for(int j = 1; j < i; j++)
- {
- ret[i][j] = ret[i-1][j] + ret[i-1][j-1];
- }
- }
- return ret;
- }
- };
输入格式:
第一个行一个正整数 n ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式:
单独的一行,包含那个可能得到的最大的和。
数据范围:
1 ≤ n ≤ 1000,三角形数字值在 [0,100] 范围内。
示例:
输入:
- 输入:
-
- 5
- 7
- 3 8
- 8 1 0
- 2 7 4 4
- 4 5 2 6 5
-
- 输出:
- 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]就是所求
- #include<stdio.h>
- #include<algorithm>
- using namespace std;
-
- int func[1005][1005] = {0};
-
- int main()
- {
- int n = 0;
- scanf("%d", &n);
- int i = 0;
- int j = 0;
- for(i = 0; i < n; i++)
- {
- for(j = 0; j <= i; j++)
- {
- scanf("%d", &func[i][j]);
- }
- }
- //假设func[i][j]表示的是从i, j到最后一层的最大路径之和
- //找出递推关系: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]就是所求
- for(i = n - 2; i >= 0; i--)
- {
- for(j = 0; j <= i; j++)
- {
- func[i][j] += max(func[i+1][j], func[i+1][j+1]);
- }
- }
- printf("%d\n", func[0][0]);
- return 0;
- }
以上内容转载自【蓝桥杯】最难算法没有之一· 动态规划真的这么好理解?(引入)_安然无虞的博客-CSDN博客_最难算法
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。