精华内容
下载资源
问答
  • 2021-11-04 14:32:30

    今天这篇文章,我们来谈一谈算法中的一种思想————动态规划。

    可能有些读者有接触过动态规划,可能也有一些读者以前完全不知道动态规划这个东西,别担心,我这篇文章会为读者做一个入门,好让读者掌握这个重要的知识点。

    首先,读者需要知道,动态规划实质上是一种思想,并不是以中具体的算法,在面对某些问题的啥时候,我们可以利用动态规划这个思想将问题转化,从而达到解决问题的地步。

    补充一点:动态规划简称dp(全称dynamic programming

    我们通过一下三个问题来了解动态规划。

    问题一:现在有一个n阶的台阶,你一次只能上一步或两步,请问你到第n阶台阶的方法数有多少?这个问题算是动态规划中最简单的问题了,读者可以自己先思考一会,然后在看解析。

    首先,我们来分析一下问题,其实不难发现,我们假设到达第n阶台阶的方法数位dp [n], 那么事实上到达第n阶的方法数就等于到达n - 1阶的方法数加上到达n - 2阶的方法数,所以我们就可以就可以写出关系式 dp[n] = dp[n - 1] + dp[n - 2] 。这个关系式我们把它叫做动态转移方程,可能有眼尖的读者已经可以发现,这不就是数学上的递推式吗?如果你能看出来,那么恭喜你,你很有潜质!

    此题的代码实现如下:

    #include <iostream>
    using namespace std;
    int dp[100] = { 1,1 };
    int main()
    {
    	int n;//n表示台阶数
    	cin >> n;
    	for (int i = 2; i <= n; i++)
    	{
    		dp[n] = dp[n - 1] + dp[n - 2];
    	}
    	cout << dp[n];
    	return 0;
    }

    如果这道题没有运用动态规划的思想,那么正常思考难度极大,但是我们运用动态规划思想,就轻松的将问题迎刃而解了。

    问题二:相信大家已经很熟悉汉诺塔问题了,但是这次的问题是,有n个盘子,求把盘子从A针移到C针的方法数。

    这道题我们这样思考,我们首先需要三个步骤

    1:将n - 1个盘子从A针移到B针(通过C针)

    2:将一个盘子从A针移到C针

    3:将n - 1个盘子从B针移到C针(通过A针)

    我们定义dp[n] 为将n个盘子从一个针移到另外一个针的方法数

    那么原问题就会变成:

    1:将n - 1个盘子从A针移到B针(通过C针)(有dp[n - 1]钟方法)

    2:将一个盘子从A针移到C针 (有一种方法)

    3:将n - 1个盘子从B针移到C针(通过A针) (有dp[n - 1]钟方法)

    通过上述分析,我们就可以写出这道题的动态转移方程:dp[n] = 2 * dp[n - 1] + 1

    所以,我们就可以码出代码,本题代码实现如下:

    #include <iostream>
    using namespace std;
    #define max 100
    int dp[max] = {0,1};
    int main()
    {
    	int n; //n代表有几个碟子
    	cin >> n;
    	for (int i = 2; i <= n; i++)
    	{
    		dp[i] = 2 * dp[i - 1] + 1;
    	}
    	cout << dp[n];
    	return 0;
    }

    这题也是一样,正常去思考难度极大,但是通过动态规划,我们也是将问题迎刃而解了。

    相信看到这里,读者已经对动态规划有了一定的了解,接下来这题将是本文的最后一道例题,同时也是最难的一道。

    题目:现在假设:你有足够的长度分别为1,2,3,……,n的长条积木,你有多少种搭出高度为h的上升三角塔(每个积木横着放,高度都为1)”
    解释:积木横着搭高,上面的积木长度不得大于下面的积木,例如高度为4,从上往下积木的长度分别为1223和1234为上升三角塔,但1232不是上升三角塔。

    输入要求:只有一行包括两个正整数n, h(0< n < 40, 0 < h < 40),n代表长条积木的长度分别为1,2,3,……,n,h代表要搭出的高度
    注意:每个长度(1,2,3,……,n)的积木的数量都是充足的,不用担心不够搭。
    保证答案能用long long存下。

    输出要求:输出一行包括一个正整数,代表方案数

    输入样例:3 3

    输出样例 10

    提示:

    对于第一个样例,10种分别为
    111
    112
    113
    122
    123
    133
    222
    223
    233
    333

    仔细读完题目后,可能读者回想用穷举法来实现,因为我可以一一列举,但事实上,这题是没有办法用列举法实现的,因为高度和长度都是未知的,但是我们编写的程序又是有界的,所以没办法用列举法,但是本题的难点就在于分析出它是一个动态规划问题。

    我们这样去思考,在排列过程中,我们不难发现,第m层长度为k的方法数为第m - 1层从长度为k到n的累加,当h = 1时(高度为1),这时候我们的方法数就是n。

    通过以上分析,我们就可以写出其对应的动态转移方程。

    我们定义,第m层长度为k时的方法数为dp[m][k]。

    此时就会有dp[m][k] = dp[m - 1][ k ] + dp[m - 1][k + 1] + .... + dp[m - 1] [n]

     求完每层长度为k的方法数之后,我们再将其全部累加之后就是我们所要的答案

    代码实现如下:

    #include <iostream>
    using namespace std;
    long long dp[50][50];
    long long sum = 0;
    int main()
    {
    	int n, h;
    	cin >> n >> h;
    	for (int i = 1; i < 49; i++)
    	{
    		dp[1][i] = 1;
    		for (int k = 1; k < 49; k++)
    			dp[i + 1][k] = 0;
    	}
    	for (int m = 2; m <= h; m++)
    	{
    		for (int j = 2; j <= n; j++)
    		{
    			for (int k = j; k <= n; k++)
    			{
    				dp[m][j] += dp[m - 1][k];
    			}
    		}
    	}
    	for (int m = 1; m <= h; m++)
    	{
    		for (int k = 1; k <= n; k++)
    		{
    			sum += dp[m][k];
    		}
    	}
    	cout << sum;
    	return 0;
    }

    好了,以上就是本文的全部内容了。

    回顾一下,本文浅谈动态规划思想,在解决某些问题是堪称神器,但是难点在于如何去分析该问题为一个动态规划问题,本文所写的还不能让读者可以完全掌握动态规划(因为作者也学了没多久换哈哈哈)但主要还是给读者做一个入门,让读者可以先了解一下动态规划是什么,这也是我写这篇文章的初衷,谢谢。

    更多相关内容
  • 本文实例讲述了动态规划之矩阵连乘问题Python实现方法。分享给大家供大家参考,具体如下: 给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算...
  • 18级学姐自主完成的算法作业,呕心沥血,基于四舍五入等于0基础的python实现,如果在语言规范上存在不足,那就。就憋着!哈哈哈哈哈,代码仅供参考,自己亲自码代码更酸爽!
  • 动态规划难吗?说实话,我觉得很难,特别是对于初学者来说,我当时入门动态规划的时候,是看 0-1 背包问题,当时真的是一脸懵逼。后来,我遇到动态规划的题,看的懂答案,但就是自己不会做,不知道怎么下手。就像做...

    动态规划难吗?说实话,我觉得很难,特别是对于初学者来说,我当时入门动态规划的时候,是看 0-1 背包问题,当时真的是一脸懵逼。后来,我遇到动态规划的题,看的懂答案,但就是自己不会做,不知道怎么下手。就像做递归的题,看的懂答案,但下不了手,关于递归的,我之前也写过一篇套路的文章,如果对递归不大懂的,强烈建议看一看:为什么你学不会递归,告别递归,谈谈我的经验

    对于动态规划,春招秋招时好多题都会用到动态规划,一气之下,再 leetcode 连续刷了几十道题

    在这里插入图片描述

    之后,豁然开朗 ,感觉动态规划也不是很难,今天,我就来跟大家讲一讲,我是怎么做动态规划的题的,以及从中学到的一些套路。相信你看完一定有所收获

    如果你对动态规划感兴趣,或者你看的懂动态规划,但却不知道怎么下手,那么我建议你好好看以下,这篇文章的写法,和之前那篇讲递归的写法,是差不多一样的,将会举大量的例子。如果一次性看不完,建议收藏,同时别忘了素质三连

    为了兼顾初学者,我会从最简单的题讲起,后面会越来越难,最后面还会讲解,该如何优化。因为 80% 的动规都是可以进行优化的。不过我得说,如果你连动态规划是什么都没听过,可能这篇文章你也会压力山大。

    一、动态规划的三大步骤

    动态规划,无非就是利用历史记录,来避免我们的重复计算。而这些历史记录,我们得需要一些变量来保存,一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤,

    如果你听不懂,也没关系,下面会有很多例题讲解,估计你就懂了。之所以不配合例题来讲这些步骤,也是为了怕你们脑袋乱了

    第一步骤:定义数组元素的含义,上面说了,我们会用一个数组,来保存历史数组,假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点,就是规定你这个数组元素的含义,例如你的 dp[i] 是代表什么意思?

    第二步骤:找出数组元素之间的关系式,我觉得动态规划,还是有一点类似于我们高中学习时的归纳法的,当我们要计算 dp[n] 时,是可以利用 dp[n-1],dp[n-2]…dp[1],来推出 dp[n] 的,也就是可以利用历史数据来推出新的元素值,所以我们要找出数组元素之间的关系式,例如 dp[n] = dp[n-1] + dp[n-2],这个就是他们的关系式了。而这一步,也是最难的一步,后面我会讲几种类型的题来说。

    学过动态规划的可能都经常听到最优子结构,把大的问题拆分成小的问题,说时候,最开始的时候,我是对最优子结构一梦懵逼的。估计你们也听多了,所以这一次,我将换一种形式来讲,不再是各种子问题,各种最优子结构。所以大佬可别喷我再乱讲,因为我说了,这是我自己平时做题的套路。

    第三步骤:找出初始值。学过数学归纳法的都知道,虽然我们知道了数组元素之间的关系式,例如 dp[n] = dp[n-1] + dp[n-2],我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n],但是,我们得知道初始值啊,例如一直推下去的话,会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了,所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值,而这,就是所谓的初始值

    由了初始值,并且有了数组元素之间的关系式,那么我们就可以得到 dp[n] 的值了,而 dp[n] 的含义是由你来定义的,你想求什么,就定义它是什么,这样,这道题也就解出来了。

    不懂?没事,我们来看三四道例题,我讲严格按这个步骤来给大家讲解。

    二、案例详解

    案例一、简单的一维 DP

    问题描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    (1)、定义数组元素的含义

    按我上面的步骤说的,首先我们来定义 dp[i] 的含义,我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法,那我们就定义 dp[i] 的含义为:跳上一个 i 级的台阶总共有 dp[i] 种跳法。这样,如果我们能够算出 dp[n],不就是我们要求的答案吗?所以第一步定义完成。

    (2)、找出数组元素间的关系式

    我们的目的是要求 dp[n],动态规划的题,如你们经常听说的那样,就是把一个规模比较大的问题分成几个规模比较小的问题,然后由小的问题推导出大的问题。也就是说,dp[n] 的规模为 n,比它规模小的是 n-1, n-2, n-3… 也就是说,dp[n] 一定会和 dp[n-1], dp[n-2]…存在某种关系的。我们要找出他们的关系。

    那么问题来了,怎么找?

    这个怎么找,是最核心最难的一个,我们必须回到问题本身来了,来寻找他们的关系式,dp[n] 究竟会等于什么呢?

    对于这道题,由于情况可以选择跳一级,也可以选择跳两级,所以青蛙到达第 n 级的台阶有两种方式

    一种是从第 n-1 级跳上来

    一种是从第 n-2 级跳上来

    由于我们是要算所有可能的跳法的,所以有 dp[n] = dp[n-1] + dp[n-2]。

    (3)、找出初始条件

    当 n = 1 时,dp[1] = dp[0] + dp[-1],而我们是数组是不允许下标为负数的,所以对于 dp[1],我们必须要直接给出它的数值,相当于初始值,显然,dp[1] = 1。一样,dp[0] = 0.(因为 0 个台阶,那肯定是 0 种跳法了)。于是得出初始值:

    dp[0] = 0.
    dp[1] = 1.
    即 n <= 1 时,dp[n] = n.

    三个步骤都做出来了,那么我们就来写代码吧,代码会详细注释滴。

    int f( int n ){
    	if(n <= 1)
    	return n;
    	// 先创建一个数组来保存历史数据
    	int[] dp = new int[n+1];
    	// 给出初始值
    	dp[0] = 0;
    	dp[1] = 1;
    	// 通过关系式来计算出 dp[n]
    	for(int i = 2; i <= n; i++){
    		dp[i] = dp[i-1] + dp[-2];
    	}
    	// 把最终结果返回
    	return dp[n];
    }
    
    (4)、再说初始化

    大家先想以下,你觉得,上面的代码有没有问题?

    答是有问题的,还是错的,错在对初始值的寻找不够严谨,这也是我故意这样弄的,意在告诉你们,关于初始值的严谨性。例如对于上面的题,当 n = 2 时,dp[2] = dp[1] + dp[0] = 1。这显然是错误的,你可以模拟一下,应该是 dp[2] = 2。

    也就是说,在寻找初始值的时候,一定要注意不要找漏了,dp[2] 也算是一个初始值,不能通过公式计算得出。有人可能会说,我想不到怎么办?这个很好办,多做几道题就可以了。

    下面我再列举三道不同的例题,并且,再在未来的文章中,我也会持续按照这个步骤,给大家找几道有难度且类型不同的题。下面这几道例题,不会讲的特性详细哈。实际上 ,上面的一维数组是可以把空间优化成更小的,不过我们现在先不讲优化的事,下面的题也是,不讲优化版本。

    案例二:二维数组的 DP

    我做了几十道 DP 的算法题,可以说,80% 的题,都是要用二维数组的,所以下面的题主要以二维数组为主,当然有人可能会说,要用一维还是二维,我怎么知道?这个问题不大,接着往下看。

    问题描述

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

    问总共有多少条不同的路径?

    在这里插入图片描述

    这是 leetcode 的 62 号题:https://leetcode-cn.com/problems/unique-paths/

    还是老样子,三个步骤来解决。

    步骤一、定义数组元素的含义

    由于我们的目的是从左上角到右下角一共有多少种路径,那我们就定义 dp[i] [j]的含义为:当机器人从左上角走到(i, j) 这个位置时,一共有 dp[i] [j] 种路径。那么,dp[m-1] [n-1] 就是我们要的答案了。

    注意,这个网格相当于一个二维数组,数组是从下标为 0 开始算起的,所以 右下角的位置是 (m-1, n - 1),所以 dp[m-1] [n-1] 就是我们要找的答案。

    步骤二:找出关系数组元素间的关系式

    想象以下,机器人要怎么样才能到达 (i, j) 这个位置?由于机器人可以向下走或者向右走,所以有两种方式到达

    一种是从 (i-1, j) 这个位置走一步到达

    一种是从(i, j - 1) 这个位置走一步到达

    因为是计算所有可能的步骤,所以是把所有可能走的路径都加起来,所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

    步骤三、找出初始值

    显然,当 dp[i] [j] 中,如果 i 或者 j 有一个为 0,那么还能使用关系式吗?答是不能的,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了,所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的,相当于计算机图中的最上面一行和左边一列。因此初始值如下:

    dp[0] [0….n-1] = 1; // 相当于最上面一行,机器人只能一直往左走

    dp[0…m-1] [0] = 1; // 相当于最左面一列,机器人只能一直往下走

    撸代码

    三个步骤都写出来了,直接看代码

    public static int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
    
        int[][] dp = new int[m][n]; // 
      	// 初始化
      	for(int i = 0; i < m; i++){
          dp[i][0] = 1;
        }
      	for(int i = 0; i < n; i++){
          dp[0][i] = 1;
        }
    		// 推导出 dp[m-1][n-1]
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
    

    O(n*m) 的空间复杂度可以优化成 O(min(n, m)) 的空间复杂度的,不过这里先不讲

    案例三、二维数组 DP

    写到这里,有点累了,,但还是得写下去,所以看的小伙伴,你们可得继续看呀。下面这道题也不难,比上面的难一丢丢,不过也是非常类似

    问题描述

    给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

    **说明:**每次只能向下或者向右移动一步。

    举例:
    输入:
    arr = [
      [1,3,1],
      [1,5,1],
      [4,2,1]
    ]
    输出: 7
    解释: 因为路径 1→3→1→1→1 的总和最小。
    

    和上面的差不多,不过是算最优路径和,这是 leetcode 的第64题:https://leetcode-cn.com/problems/minimum-path-sum/

    还是老样子,可能有些人都看烦了,哈哈,但我还是要按照步骤来写,让那些不大懂的加深理解。有人可能觉得,这些题太简单了吧,别慌,小白先入门,这些属于 medium 级别的,后面在给几道 hard 级别的。

    步骤一、定义数组元素的含义

    由于我们的目的是从左上角到右下角,最小路径和是多少,那我们就定义 dp[i] [j]的含义为:当机器人从左上角走到(i, j) 这个位置时,最下的路径和是 dp[i] [j]。那么,dp[m-1] [n-1] 就是我们要的答案了。

    注意,这个网格相当于一个二维数组,数组是从下标为 0 开始算起的,所以 由下角的位置是 (m-1, n - 1),所以 dp[m-1] [n-1] 就是我们要走的答案。

    步骤二:找出关系数组元素间的关系式

    想象以下,机器人要怎么样才能到达 (i, j) 这个位置?由于机器人可以向下走或者向右走,所以有两种方式到达

    一种是从 (i-1, j) 这个位置走一步到达

    一种是从(i, j - 1) 这个位置走一步到达

    不过这次不是计算所有可能路径,而是计算哪一个路径和是最小的,那么我们要从这两种方式中,选择一种,使得dp[i] [j] 的值是最小的,显然有

    dp[i] [j] = min(dp[i-1][j],dp[i][j-1]) + arr[i][j];// arr[i][j] 表示网格种的值
    
    步骤三、找出初始值

    显然,当 dp[i] [j] 中,如果 i 或者 j 有一个为 0,那么还能使用关系式吗?答是不能的,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了,所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的,相当于计算机图中的最上面一行和左边一列。因此初始值如下:

    dp[0] [j] = arr[0] [j] + dp[0] [j-1]; // 相当于最上面一行,机器人只能一直往左走

    dp[i] [0] = arr[i] [0] + dp[i] [0]; // 相当于最左面一列,机器人只能一直往下走

    代码如下
    public static int uniquePaths(int[][] arr) {
      	int m = arr.length;
      	int n = arr[0].length;
        if (m <= 0 || n <= 0) {
            return 0;
        }
    
        int[][] dp = new int[m][n]; // 
      	// 初始化
      	dp[0][0] = arr[0][0];
      	// 初始化最左边的列
      	for(int i = 1; i < m; i++){
          dp[i][0] = dp[i-1][0] + arr[i][0];
        }
      	// 初始化最上边的行
      	for(int i = 1; i < n; i++){
          dp[0][i] = dp[0][i-1] + arr[0][i];
        }
    		// 推导出 dp[m-1][n-1]
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
            }
        }
        return dp[m-1][n-1];
    }
    

    O(n*m) 的空间复杂度可以优化成 O(min(n, m)) 的空间复杂度的,不过这里先不讲

    案例 4:编辑距离

    这次给的这道题比上面的难一些,在 leetcdoe 的定位是 hard 级别。好像是 leetcode 的第 72 号题。

    问题描述

    给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。

    你可以对一个单词进行如下三种操作:

    插入一个字符
    删除一个字符
    替换一个字符

    输入: word1 = "horse", word2 = "ros"
    输出: 3
    解释: 
    horse -> rorse (将 'h' 替换为 'r')
    rorse -> rose (删除 'r')
    rose -> ros (删除 'e')
    

    解答

    还是老样子,按照上面三个步骤来,并且我这里可以告诉你,90% 的字符串问题都可以用动态规划解决,并且90%是采用二维数组。

    步骤一、定义数组元素的含义

    由于我们的目的求将 word1 转换成 word2 所使用的最少操作数 。那我们就定义 dp[i] [j]的含义为:当字符串 word1 的长度为 i,字符串 word2 的长度为 j 时,将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]

    有时候,数组的含义并不容易找,所以还是那句话,我给你们一个套路,剩下的还得看你们去领悟。

    步骤二:找出关系数组元素间的关系式

    接下来我们就要找 dp[i] [j] 元素之间的关系了,比起其他题,这道题相对比较难找一点,但是,不管多难找,大部分情况下,dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。因为我们的目标就是,从规模小的,通过一些操作,推导出规模大的。对于这道题,我们可以对 word1 进行三种操作

    插入一个字符
    删除一个字符
    替换一个字符

    由于我们是要让操作的次数最小,所以我们要寻找最佳操作。那么有如下关系式:

    一、如果我们 word1[i] 与 word2 [j] 相等,这个时候不需要进行任何操作,显然有 dp[i] [j] = dp[i-1] [j-1]。(别忘了 dp[i] [j] 的含义哈)。

    二、如果我们 word1[i] 与 word2 [j] 不相等,这个时候我们就必须进行调整,而调整的操作有 3 种,我们要选择一种。三种操作对应的关系试如下(注意字符串与字符的区别):

    (1)、如果把字符 word1[i] 替换成与 word2[j] 相等,则有 dp[i] [j] = dp[i-1] [j-1] + 1;

    (2)、如果在字符串 word1末尾插入一个与 word2[j] 相等的字符,则有 dp[i] [j] = dp[i] [j-1] + 1;

    (3)、如果把字符 word1[i] 删除,则有 dp[i] [j] = dp[i-1] [j] + 1;

    那么我们应该选择一种操作,使得 dp[i] [j] 的值最小,显然有

    dp[i] [j] = min(dp[i-1] [j-1],dp[i] [j-1],dp[[i-1] [j]]) + 1;

    于是,我们的关系式就推出来了,

    步骤三、找出初始值

    显然,当 dp[i] [j] 中,如果 i 或者 j 有一个为 0,那么还能使用关系式吗?答是不能的,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了,所以我们的初始值是计算出所有的 dp[0] [0….n] 和所有的 dp[0….m] [0]。这个还是非常容易计算的,因为当有一个字符串的长度为 0 时,转化为另外一个字符串,那就只能一直进行插入或者删除操作了。

    代码如下
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        // dp[0][0...n2]的初始值
        for (int j = 1; j <= n2; j++) 
        	dp[0][j] = dp[0][j - 1] + 1;
        // dp[0...n1][0] 的初始值
        for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
    		// 通过公式推出 dp[n1][n2]
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
              	// 如果 word1[i] 与 word2[j] 相等。第 i 个字符对应下标是 i-1
                if (word1.charAt(i - 1) == word2.charAt(j - 1)){
                	p[i][j] = dp[i - 1][j - 1];
                }else {
                   dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
                }         
            }
        }
        return dp[n1][n2];  
    }
    

    最后说下,如果你要练习,可以去 leetcode,选择动态规划专题,然后连续刷几十道,保证你以后再也不怕动态规划了。当然,遇到很难的,咱还是得挂。

    Leetcode 动态规划直达:https://leetcode-cn.com/tag/dynamic-programming/

    三、总结

    上面的这些题,基本都是不怎么难的入门题,除了最后一道相对难一点,本来是要在写几道难一点,并且讲如何优化的,不过看了下字数,文章有点长了,关于如何优化的,后面再讲吧,在之后的文章中,我也会按照这个步骤,在给大家讲四五道动态规划 hard 级别的题,会放在每天推文的第二条给大家学习。如果大家感兴趣,文章看的人多,那么优化篇很快就会撸出来,大家想要第一时间观看我的文章的,可以关注我的个人微信公众号『苦逼的码农』,不过感兴趣的人很少的话,动力比较少,可能就会慢一些,所以各位小伙伴,如果觉得有收获,不放三连走起来,嘻嘻。

    有收获?希望老铁们来个三连击,给更多的人看到这篇文章

    1、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。

    2、老铁们,关注我的原创微信公众号「帅地玩编程」,专注于写算法 + 计算机基础知识(计算机网络+ 操作系统+数据库+Linux)。

    保存让你看完有所收获,不信你打我。后台回复『电子书』送你一份精选电子书大礼包,包含各类技能的优质电子书。

    展开全文
  • 这个是动态规划之跳跃点0-1背包问题,如果只是想要动态规划0-1背包问题求解代码,请到主页查看。18级学姐自主完成的算法作业,呕心沥血,基于四舍五入等于0基础的python实现,如果在语言规范上存在不足,那就。就憋...
  • 动态规划算法

    千次阅读 2022-01-19 11:12:57
    动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法 动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,...

    1. 应用场景-背包问题

    背包问题:有一个背包,容量为4磅 , 现有如下物品
    请添加图片描述
    要求如下:

    1. 要求达到的目标为装入的背包的总价值最大,并且重量不超出
    2. 要求装入的物品不能重复

    2. 动态规划算法介绍

    1. 动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法

    2. 动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

    3. 与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解 )

    4. 动态规划可以通过填表的方式来逐步推进,得到最优解.

    3. 思路

    算法的主要思想,利用动态规划来解决。每次遍历到的第i个物品,根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品,设v[i]、w[i]分别为第i个物品的价值和重量,C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。

    构建表格
    请添加图片描述

    上图中:第一行全部为0,表示前0个物品中能够装入容量为1,2,3,4磅的物品的价值都为0,因为前0个物品就是一个物品都没有,所以,无论背包有多少磅,其装入的价值都为0。第一列全部为0,就是背包可以装入的重量为0磅,所以什么物品都不能放入其中。

    请添加图片描述
    上图中,v[1][1]中背包能够承受1磅,在前一个物品中选择,前一个物品就只有吉他,所以就只能选择吉他进入包中,价值为v[1][1]=1500。v[1][2]中背包能够装入2磅,从前一个物品中选择,所以还是只能选择吉他 v[1][2] = 1500。注意不能重复放入物品,所以v[1][2] = 1500 而不是3000。v[1][3],v[1][4]同理。

    请添加图片描述
    上图中,v[2][1]中,背包能够承受1磅,可以选择的物品是前两个物品即吉他(1磅)和音响(4磅),所以只能选择吉他,所以v[2][1]的值是拷贝自v[1][1]的值。 即v[2][1]的上一格。 v[2][2]中,背包能够承受2磅,还是只能存放吉他,所以v[2][2]的值是拷贝自v[1][2]的值。 v[2][3]同理,v[2][4]中,背包能够承受4磅,吉他和音响不能同时入包,只能选择一个,所以选择价值大的音响。所以v[2][4] = 3000.

    请添加图片描述
    上图中,v[3][1]只能承受1磅,从前三个物品中选择(吉他,音响,电脑),由于只能承受1磅,所以只能选择吉他,所以v[3][1] = 1500 拷贝自v[2][1]. v[3][2]同理。v[3][3]中能够承受3磅,所以选择电脑,所以v[3][3] = 2000. v[3][4]中可以承受4磅,所以可以选择吉他和电脑或者只选择音响,因为吉他和电脑的总价值比音响大,所以选择吉他和电脑,所以v[3][4] = 3500.

    总结
    算法的主要思想,利用动态规划来解决。每次遍历到的第i个物品,根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品,设v[i]、w[i]分别为第i个物品的价值和重量,C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。

    (1) v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是0

    (2) 当w[i]> j 时:v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于 当前背包的容量时,就直接使用上一个单元格的装入策略

    (3) 当j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} // 当准备加入的新增的商品的容量小于等于当前背包的容量.

    装入的方式:

    v[i-1][j]: 就是上一个单元格的装入的最大值

    v[i] : 表示当前商品的价值

    v[i-1][j-w[i]] : 装入i-1商品,到剩余空间j-w[i]的最大值

    4. 代码实现

    public class KnapsackProblem {
        public static void main(String[] args) {
            int[] w = {1, 4, 3}; // 保存物品的数量
            int[] val = {1500, 3000, 2000}; // 物品的价值
            int m = 4; // 背包的容量
            int n = val.length; // 物品的个数
            int[][] v = new int[n + 1][m + 1]; // 二维数组 v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。
    
    
            // 初始化第一行和第一列
            for (int i = 0; i < v.length; i++) {
                v[i][0] = 0;
            }
            for (int i = 0; i < v[0].length; i++) {
                v[0][i] = 0;
            }
    
            // 开始处理
            for (int i = 1; i < v.length; i++) {
                for (int j = 1; j < v[0].length; j++) {
                    // 公式
                    if (w[i - 1] > j) {
                        v[i][j] = v[i - 1][j];
                    } else {
                        v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    }
                }
            }
    
    
            // 输出二维数组
            for (int i = 0;i<v.length;i++){
                System.out.println(Arrays.toString(v[i]));
            }
    
        }
    }
    
    

    请添加图片描述

    展开全文
  • 设有n种不同面值的硬币,第i种硬币的币值是vk(其中v1=1),重量是wi,i=1,2……n,且现在购买某些总价值为y的商品,需要用这些硬币付款,如果每种钱币使用的个数不限,那么如何选择付款的方法是的付出钱币的总重量最轻?
  • C++动态规划详解

    千次阅读 2021-09-11 18:30:59
    动态规划思想 一、动态规划概念: 动态规划(dp)是研究多步决策过程最优化问题的一种数学方法。在动态规划中,为了寻找一个问题的最优解(即最优决策过程),将整个问题划分成若干个相应的阶段,并在每个阶段都...

    动态规划思想

    一、动态规划概念:

    • 动态规划(dp)是研究多步决策过程最优化问题的一种数学方法。在动态规划中,为了寻找一个问题的最优解(即最优决策过程),将整个问题划分成若干个相应的阶段,并在每个阶段都根据先前所作出的决策作出当前阶段最优决策,进而得出整个问题的最优解。即记住已知问题的答案,在已知的答案的基础上解决未知的问题。

    • 在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。可以自行创建一个动态规划表dp,dp一般是个数组,可以是一维也可以是二维数组,根据题中的需要,然后将子问题的最优解填入其中,方便在求解之后的子问题时可以方便调用,进而求出整个问题的最优解。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

    • 动态规划有两种实现方法,一种是递推,另一种是记忆化搜索。两种方法时间复杂度完全相同,但是,递推的效率要比记忆化搜索高不少,而且以后的大量优化技巧都建立在递推上(滚动数组、单调队列、斜率优化……)。所以,我们一般用递推来写动态规划。

    二、动态规划的性质:

    (1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

    (2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

    (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

    三、动规解题的一般思路:

    动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。

    初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

    (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。

    (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。

    (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

    (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。 一般,只要解决问题的阶段、状态和状态转移决策确定了,就可以写出状态转移方程(包括边界条件)。

    四、解题步骤:

    • 拆分问题;

    • 定义状态并找出初状态;

    • 状态转移方程。

    五、算法实现的步骤:

    1、创建一个一维数组或者二维数组,保存每一个子问题的结果,具体创建一维数组还是二维数组看题目而定,基本上如果题目中给出的是一个一维数组进行操作,就可以只创建一个一维数组,如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值,比如背包问题中的不同物体的体积与总体积,找零钱问题中的不同面值零钱与总钱数,这样就需要创建一个二维数组。注:需要创建二维数组的解法,都可以创建一个一维数组运用滚动数组的方式来解决,即一位数组中的值不停的变化,后面会详细徐叙述

    2、找到初始条件,设置数组边界值,一维数组就是设置第一个数字,二维数组就是设置第一行跟第一列的值,特别的滚动一维数组是要设置整个数组的值,然后根据后面不同的数据加进来变幻成不同的值。

    3、根据初始条件或边界条件,找出状态转换方程,也就是说找到每个状态跟他上一个状态的关系,根据状态转化方程写出代码。

    4、返回需要的值,一般是数组的最后一个或者二维数组的最右下角。

    六、例题

    应用举例1:

    题目描述:超级台阶

    题目描述
    有一楼梯共m级,刚开始时你在第一级,若每次只能跨上一级或二级,要走上第m级,共有多少走法?

    注:规定从一级到一级有0种走法。

    输入格式
    输入数据首先包含一个整数n(1<=n<=100),表示测试实例的个数,然后是n行数据,每行包含一个整数m,(1<=m<=40), 表示楼梯的级数。

    输出格式
    对于每个测试实例,请输出不同走法的数量。

    输入输出样例
    输入

    2
    2
    3
    输出

    1
    2

    代码思路:

    首先考虑题中要求的是走上m级台阶总共有多少走法,不妨设dp(m) = ans;
    再考虑下子问题:
    dp(m-1) 就是走上m-1级台阶总共有多少走法
    dp(m-2)就是走上m-2级台阶总共有多少走法
    子问题与原问题的关系:题中告诉我们每次只可以跨一级或两级,那么反过来理解就是,第m级台阶可能是m-1或者m-2级台阶走上来的,如果已经求出了dp(m-1)和dp(m-2),很明显:
    dp(m) = dp(m-1)+dp(m-2);

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iluDfX2P-1631356231751)(C:\Users\86152\AppData\Roaming\Typora\typora-user-images\image-20210911151227624.png)]

    代码实现:

    #include "iostream"
    using namespace std;
    int n;
    int m,dp[3];//创建dp数组,之用来存储三级台阶
    int main(){
        cin>>n;
        for (int i = 1; i <=n ; ++i) {
            cin>>m;
            dp[0] = dp[1] = 1; // 初始化第一、二级台阶为1,这样之后的可以递推
            if(m<2){ 
                break;
            }
            for(int j=2;j<m;j++){ //从第二级开始递推
                dp[j%3] = dp[(j-1)%3]+dp[(j-2)%3];//这里使用滚动数组来优化空间
            }
            cout<<dp[(m-1)%3]<<endl;
        }
        return 0;
    }
    

    应用举例2:

    题目描述:矩阵最短路径

    给定一个矩阵m,从左上角开始每次只能向右走或者向下走,最后达到右下角的位置,路径中所有数字累加起来就是路径和,返回所有路径的最小路径和,如果给定的m如下,那么路径1,3,1,0,6,1,0就是最小路径和,返回12.

    1 3 5 9
    8 1 3 4
    5 0 6 1
    8 8 4 0

    代码思路:

    ​ 由分析可知:走到第(i ,j)个数时,只可能是从(i-1 ,j)或是(i ,j-1)走来的,路径(i ,j)的阶段依赖的是(i-1 ,j)和(i ,j-1)的子阶段,所以状态转移方程为

    dp[i][j] =a[i][j] + min(dp[i-1][j]+ dp[i][j-1])
    

    ,属于简单的动态规划问题。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-U6B1k1uq-1631356231756)(C:\Users\86152\AppData\Roaming\Typora\typora-user-images\image-20210911151251206.png)]

    代码实现:

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int dp[4][4] = {};     //全局数组,存放决策表
    int main()
    {
    	int a[4][4] = {1,3,5,9,8,1,3,4,5,0,6,1,8,8,4,0};  //矩阵存储a[i][j]
    	for (int i = 0;i < 4;++i){
    		for (int j = 0;j < 4;++j){
    			if (i==0 && j==0){//第一个初始为自身,边界条件问题需要考虑到
    				dp[i][j] = a[i][j];
    			} 
    			else if (i==0 && j!=0){ //如果是第一行的,只能从左边过来
    				dp[i][j] = a[i][j] + dp[i][j-1];
    			}
    			else if (i!=0 && j==0){ //如果是第一列的只能从上边下来
    				dp[i][j] = a[i][j] + dp[i-1][j];
    			}
    			else{ //其他情况下,就要取 从上边下来或者从左边做来 这两种中的最小值
    				dp[i][j] = a[i][j] + min(dp[i-1][j],dp[i][j-1]);
    			}
    		}
    	}
    	cout<<"走到位置"<<"(4,4)"<<"最短路径为:";
    	cout<<dp[3][3]<<endl;    
    	return 0;
    }
    

    应用举例3:

    问题描述:最长递增子序列

    给定数组arr,返回arr的最长递增子序列的长度,比如arr=[2,1,5,3,6,4,8,9,7],最长递增子序列为[1,3,4,8,9]返回其长度为5。

    思路分析:

    首先生成dp[n]的数组,dp[i]表示以必须arr[i]这个数结束的情况下产生的最大递增子序列的长度。对于第一个数来说,很明显dp[0]为1,当我们计算dp[i]的时候,我们去考察i位置之前的所有位置,找到i位置之前的最大的dp值,记为dpj,dp[j]代表以arr[j]结尾的最长递增序列,而dp[j]又是之前计算过的最大的那个值,我们在来判断arr[i]是否大于arr[j],如果大于dp[i]=dp[j]+1.计算完dp之后,我们找出dp中的最大值,即为这个串的最长递增序列。

    应用举例4:导弹拦截

    题目描述:

    某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。
    但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。
    某天,雷达捕捉到敌国的导弹来袭,由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

    输入导弹的枚数和导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,每个数据之间有一个空格)。
    计算这套系统最多能拦截多少导弹?

    【输入格式】
    第一行,数字n表示n个导弹(n<=200)
    第二行,n个数字,表示n个导弹的高度
    【输出格式】
    第一行,一个整数,表示最多能拦截的导弹数
    【样例数据】
    input:

    8
    389 207 155 300 299 170 158 65
    output:

    6

    思路分析:

    首先我们需要选择一个点,作为你要拦截的那串导弹的终点(为什么是找终点而不是找起点呢?可以通过“无后效性”分析得知,选择终点可以利用前边那些点的最优决策。
    用一个数组f[i]表示拦截到底i颗导弹时已经拦截几个了,如果第j个导弹比第i个导弹低,就说明前面肯定没有拦截到第j个。我们可以枚举1~i-1这些导弹,选择一个f数值最大的,把第i个导弹作为它的后缀,也就是说:f[i]=max{f[j]}+1;1<=j<i;

    代码展示:

    int a[50000],f[50000];
    int main()
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
     	   cin>>a[i];   //高度数组
    	int ans=0; //最大拦截数
        for(int i=1;i<=n;i++){
            f[i]=1; // f数组都初始化1,即自身一定可以拦截
            for(int j=1;j<i;j++) //从选择的那个点之前的点开始遍历
                if(a[i]<=a[j])  //如果终点前边有比终点高的,就说明终点可以被再次拦截
    				f[i]=max(f[i],f[j]+1); //需要考虑的是有可能前边有好几个点都符合,那么就要选最大的
            ans=max(ans,f[i]);//将每个点的最终状态都进行比较,取最大值,就是最大拦截数
        }
        cout<<ans<<endl;
    

    应用举例5:数组最大连续子序列和

    题目描述:

    如arr[] = {6,-1,3,-4,-6,9,2,-2,5}的最大连续子序列和为14。即为:9,2,-2,5。

    思路分析:

    思路:创建一个数组a,长度为原数组长度,不同位置数字a[i]代表0…i上最大连续子序列和,a[0]=arr[0]设置一个最大值max,初始值为数组中的第一个数字。当进来一个新的数字arr[i+1]时,判断到他前面数字子序列和a[i]+arr[i+1]跟arr[i+1]哪个大,前者大就保留前者,后者大就说明前面连续数字加起来都不如后者一个新进来的数字大,前面数字就可以舍弃,从arr[i+1]开始,每次比较完都跟max比较一下,最后的max就是最大值。越加越大。

    应用举例6:两个字符串最大公共子序列

    思路分析:

    有两个字符串s1,s2,我们用dp[][][i][j]表示s1中前i个字符与s2中前j个字符分别组成的两个前缀字符串的最长公共子串的长度。当i或j等于0时,我们可以直接得到结果等于0.用两个for循环代表s1长度为i,s2长度为j时他们的最大子序列dp[i][j]。

    若s1[i]=s2[j],由于他们都是各自子串的最后一个字符,所以必定存在一个最大子串有这个字符结尾,其他部分和 i-1、 j-1时的子串相同。

    dp[i][j]=dp[i-1][j-1]+1;
    

    相反的如果不同,那么就需要比较是s1中前i-1个字符和s2中j个字符的最大子串长还是s1中前i个字符和s2中j-1个字符的最大字串长。

    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    

    重点在于每次比较的是原来s1和s2的不同长度的子串,然后再依次往后推移,直到整个字符串都遍历。

    代码展示:

    int MaxTwoArraySameOrderMethod(string str1, string str2) {
    	int m = str1.length();
    	int n = str2.length();
    	/*
    	 * 定义一个二维数组保存公共子序列长度
    	 * dp[i][j]表示字符串1从头开始长度是i,字符串2从头开始长度是j,这两个字符串的最长公共子序列的长度
    	 * 设置数组行列比他们长度大一往二维数组中填写数字时,每个位置的数字跟他上方或者左方或者左上方数字有关系,这样处理边界数字时不用处理这种情况,方便接下来的循环
    	 */
    	int dp[m+1][n+1];
    	/*
    	 * 初始化第一行第一列
    	 * dp[0,j]表示啥?表示字符串1的长度是0,字符串2的长度是j,这两个字符串的最长公共子序列的长度是0,因为,字符串1 根本就没有嘛
    	 */
    	for (int i = 0; i <= m; i++) {
    		dp[i][0] = 0;
    	}
    	for (int i = 0; i <= n; i++) {
    		dp[0][i] = 0;
    	}
    	for (int i = 1; i <= m; i++) {
    		for (int j = 1; j <= n; j++) {
    			/*
    			 * 如果当c[i][j]时,字符串1从头开始长度是i,字符串2从头开始长度是j时他们最后一个字符相同,就同时把他们向前移动一位,找c[i-1][j-1]时长度最大的再加1
    			 * 表现在二维数组中就是c[i][j]左上方的点
    			 */
    			if (str1[i - 1] == str2[j - 1]) {
    				dp[i][j] = dp[i - 1][j - 1] + 1;
    				/*
    				 * 如果当c[i][j]时,他们最后一个字符不相同
    				 * 要将str1往前移动一位的c[i-1][j]的lcs长度,或者将str2往前移动一位的c[i][j-1]的lcs长度,哪个长,将它赋给c[i][j]
    				 * 表现在二维数组中就是c[i][j]上方的点或者左方的点
    				 */
    			}
    			else {
    				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
    			}
    		}
    	}
    	return dp[m][n];
    }
    

    应用举例7:0-1背包问题

    题目描述:

    在N件物品取出若干件放在容量为W的背包里,每件物品的体积为W1,W2……Wn(Wi为整数),与之相对应的价值为P1,P2……Pn(Pi为整数),求背包能够容纳的最大价值。

    思路分析:

    动态规划,创建一个二维数组dp,来存储每种情况下的最大价值。横坐标为物品的个数从0-n,纵坐标为容量从0-w,可以知道无论是物品数为0,还是容量为0,价值都是0,可以作为起始条件。

    对每个容量去分析这些物品哪些能放进去,总共能放进去几个,如果能放进去,需要考虑放不放,放的话价值变为 dp[i][j-w[i]]+p[i](意思就是放同样的个数之前那个容量能放的再加上现在这个),如果能放但不放,价值和dp[i-1][j](容量一样,但个数少一个)一样,取这两个中较大。

    如果不能放,同样是dp[i-1][j]。

    代码展示:

    int PackageHelper(int n, int w[], int p[], int v) {
            // n物品个数,w体积,p价值,v容量
    	//设置一个二维数组,横坐标代表从第一个物品开始放到第几个物品,纵坐标代表背包还有多少容量,dp代表最大价值
     	int dp[n+1,v+1];
     	
    	for (int i = 0; i < n + 1; i++) {
    		dp[i][0] = 0;
    	}
     
    	for (int i = 0; i < v + 1; i++) {
    		dp[0][i] = 0;
    	}
     
    	for (int i = 1; i < n + 1; i++) {
    		for (int j = 1; j < v+1; j++) {
    			if (j >= w[i-1]) {
    				/*
    				 * 当能放得下这个物品时,放下这个物品,价值增加,但是空间减小,最大价值是dp[i-1][j-w[i]]+p[i]
    				 * 当不放这个物品时,空间大,物品还是到i-1,最大价值是dp[i-1][j]
    				 * 比较这两个大小,取最大的,就是dp[i][j]
    				 */
    				dp[i][j] = max(dp[i - 1][j], dp[i ][j - w[i-1]] + p[i-1]);
    			}
    			else {
    				//如果放不下,就是放上一个物品时的dp
    				dp[i][j] = dp[i - 1][j];
    			}
    		}
    	}
     
    	return dp[n][v];
    }
    

    应用举例8:找零钱问题

    问题描述:

    有数组penny,penny中所有的值都为正数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim(小于等于1000)代表要找的钱数,求换钱有多少种方法。给定数组penny及它的大小(小于等于50),同时给定一个整数aim,请返回有多少种方法可以凑成aim。

    思路分析:

       设dp[i][j]代表钱为j,i纸币的面值时共有的找钱方法。先找到每种面值的解决方法,然后递推,逐步再求出所有面值都有的时候的找钱方法。
       如果钱j为0,那么方法肯定为0。如果钱数是第一种纸币的面值的整数倍,那么只有1种方法,或者0种方法,这是初始条件。
       之后对钱和面值开始遍历,如果钱数大于面值(证明可以找零钱),那么方法数= 面值是前边一种,钱数不变的的时候的方法  +   面值不变,钱数=钱数-面值 时的方法(dp[i][j] = dp[i - 1][j] + dp[i][j - penny[i]])。因为,对于某种面值我们有两种情况,用或不用,不用就是dp[i - 1][j]  ,用了,那么此时的钱就必须先减取面值,j-penny[i],所以是dp[i][j - penny[i]]。至于考虑用的张数,这个会在遍历钱j的时候考虑到。
    
    int countWays(int penny[], int n, int aim) {
                  //penny 面值数组, 面值个数,aim 总钱数
     	int dp[n][aim+1];
    	//初始状态
    	for (int i = 0; i < n; i++) dp[i][0] = 1;//aim=0时
    	for (int j = 1; j <= aim; j++) {//第一行
    		int i = penny[0];
    		if (j%i == 0)
    			dp[0][j] = 1;
    		else dp[0][j] = 0;
     
    	}
    	//从上到下 从左到右
    	for (int i = 1; i < n; i++) {
    		for (int j = 1; j <= aim; j++) {
    			if (j >= penny[i]) {//在前i-1项里面拼凑j,和在前i项里拼凑j-penny[i]--默认已经选择一个i
    				dp[i][j] = dp[i - 1][j] + dp[i][j - penny[i]]; //  不用 + 用
    			}
    			else {
    				dp[i][j] = dp[i - 1][j]; // 不用
    			}
    		}
    	}
    	return dp[n - 1][aim];
    }
    
    展开全文
  • 动态规划经典例题详解

    千次阅读 2021-12-28 17:39:51
    运用的是动态规划的思想,由于是求最长回文字符串。 dp数组定义为:在子串s[i…j]中,最长回文子序列的长度为dp[i][j]; 子问题: 所以其子问题可以看作是求短一点长度,例如求dp[i][j],可 以由求其子问题dp[i+1][j-...
  • 动态规划系列—动态规划VS回溯算法

    千次阅读 2020-09-19 16:14:20
    动态规划和回溯算法看起来有挺多共同之处,都涉及到了【递归】和【做选择】,那么他们之间区分在哪里呢?以及这两者之间是否能够转化? 通常来讲,我们使用回溯算法去遍历的时候,就是在使用暴力穷举的方法,当数据...
  • 动态规划(C语言)

    千次阅读 2022-03-22 15:18:04
    动态规划问题解决的基本思想: 1、根绝问题所求的那一项和变量的个数,确定是一维数组,二维数组或者多维数组。 2、写出初始值,一般是某个变量为1或者0 的特殊情况时候的解。 3、通过循环,一般是两个循环中间每一...
  • 动态规划——导弹拦截
  • 动态规划-01背包

    2022-03-06 17:49:57
    动态规划中的01背包问题
  • 动态规划玩游戏

    千次阅读 2021-11-18 10:09:39
    动态规划之最小路径和64. 最小路径和 1. 动态规划之最小路径和 64. 最小路径和 给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下...
  • 动态规划是我最早接触的算法,一开始非常简单,固定模板题,后来愈发愈发难起来了,条件,状态压缩等等,难点主要是,状态怎么表示,状态转移方程怎么写,这篇文章将会从背包五大问题详解,希望能帮助到大家去类比,...
  • 动态规划

    千次阅读 2020-08-07 21:05:35
    1. 什么是动态规划 从数学的视角来看,动态规划是一种运筹学方法,是在多轮决策过程中的最优方法。 那么,什么是多轮决策呢?其实多轮决策的每一轮都可以看作是一个子问题。从分治法的视角来看,每个子问题必须相互...
  • leetcode找零钱问题动态规划 2020.10.12开启每日刷题模式。这里记录每日刷题进展与代码目录情况~ 如果对时间复杂度的要求有 \loglog,通常都需要用到二分查找。 动态规划: 数据结构的存储方式只有两种:数组(顺序...
  • 动态规划是经典算法的一种。在算法中动态规划算法的重要性不容置疑,本博客主要是记载自己在刷题和学习过程中对动态规划的一个理解和总结。 动态规划 定义 动态规划算法是通过拆分问题,定义问题状态和状态之间的...
  • 【刷题日记】动态规划经典题目

    千次阅读 多人点赞 2022-02-14 14:43:39
    ????大家好,我是白晨,一个不是很能熬夜????,但是也想日更的人✈。如果喜欢这篇文章,点个赞????,关注一下????白晨吧!...动态规划经典题目?...观前提醒:这篇文章需要一定动态规划的基础???? ????
  • 动态规划】求路径

    多人点赞 2021-12-14 23:46:40
    今天解一道动态规划问题中较为简单易于理解的一题,求路径 牛客链接 题目:一个机器人在m×n大小的地图的左上角(起点)。 机器人每次可以向下或向右移动。机器人要到达地图的右下角(终点)。 可以有多少种不同的...
  • 动态规划——矩阵链相乘

    千次阅读 2022-04-21 17:29:06
    动态规划之矩阵链相乘
  • 动态规划之背包问题——01背包

    千次阅读 多人点赞 2021-11-24 15:56:06
    算法相关数据结构总结: 序号 数据结构 文章 1 动态规划 动态规划之背包问题——01背包 动态规划之背包问题——完全背包 动态规划之打家劫舍系列问题 动态规划之股票买卖系列问题 动态规划之子序列问题 算法(Java)...
  • Java 动态规划

    万次阅读 多人点赞 2019-06-23 16:16:43
    Java中的动态规划 介绍 动态规划典型的被用于优化递归算法,因为它们倾向于以指数的方式进行扩展。动态规划主要思想是将复杂问题(带有许多递归调用)分解为更小的子问题,然后将它们保存到内存中,这样我们就不必在...
  • 教你彻底学会动态规划——入门篇

    万次阅读 多人点赞 2015-08-11 13:26:41
    动态规划相信大家都知道,动态规划算法也是新手在刚接触算法设计时很苦恼的问题,有时候觉得难以理解,但是真正理解之后,就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章,大多都是...
  • 动态规划算法典型例题

    万次阅读 多人点赞 2020-05-02 12:08:07
    1. 动态规划之选数问题 题目要求: 假设给定一串数字{1, 2, 4, 1, 7, 8, 3},我们要从中选择若干个数,使最后的和达到最大。选择的规则是,不能选相邻的数字。比如:如果我们选了第一个数字1,那么我们就不能选2,...
  • 动态规划——状态转移方程

    千次阅读 2022-01-17 16:16:19
    DP问题的核心即确定动态转移方程。 (1)寻找变量,确定子问题。DP表一般为二维,故需要两个变量。 (2)寻找总问题与子问题迭代关系,确定中间值、迭代值 例1: 有5个物品,其重量分别是{2, 2, 6, 5, 4},价值...
  • 动态规划之滚动数组

    2022-03-12 23:39:05
    动态规划中关于滚动数组的问题
  • 01背包问题(动态规划解决)

    千次阅读 2021-09-08 16:35:13
    动态规划原理 动态规划的核心:填表 动态规划和分治法的相同点:把大问题拆分成小问题,再找大小问题间的递推关系。由最基本的小问题开始解决,逐渐解决大问题。 动态规划和分治法的不同点:分治法不会记忆中间的...
  • 最长公共子串 动态规划,详细注释
  • ACM总结——动态规划

    千次阅读 2020-05-29 01:27:48
    动态规划(dynamic programming)简称DP。 先看3个简单的问题: 1,斐波那契数列 1,1,2,3,5,8...... 求第n项 int fac(int n) { if(n<3)return 1; return fac(n-1)+fac(n-2); } 时间复杂度O (1.6 ^ n) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 67,134
精华内容 26,853
关键字:

动态规划等于