精华内容
下载资源
问答
  • 什么样的问题适合使用动态规划
    千次阅读
    2020-07-12 09:59:11

    可以使用动态规划的问题一般都有一些特点可以遵循。如题目的问法一般是三种方式:

    1.求最大值/最小值

    2.求可不可行

    3.求方案总数

    如果碰到一个问题,是问这三个问题之一的,就有90%概率是使用动态规划来求解。

    重点说明的是,如果一个问题是让求出所有的方案和结果,则肯定不是使用动态规划。

    更多相关内容
  • 你没有系统地总结过究竟有哪些问题可以用动态规划解决。 知己知彼,你想把动态规划作为你的面试武器之一,就得足够了解它;而应对面试,总结、归类问题其实是个不错的选择,这我们刷题的时候其实也能感觉得到。...

    说起动态规划,我不知道你有没有这样的困扰,在掌握了一些基础算法和数据结构之后,碰到一些较为复杂的问题还是无从下手,面试时自然也是胆战心惊。如果我说动态规划是个玄幻的问题其实也不为过。究其原因,我觉得可以归因于这样两点:

    • 你对动态规划相关问题的套路和思想还没有完全掌握;
    • 你没有系统地总结过究竟有哪些问题可以用动态规划解决。

    知己知彼,你想把动态规划作为你的面试武器之一,就得足够了解它;而应对面试,总结、归类问题其实是个不错的选择,这在我们刷题的时候其实也能感觉得到。那么,我们就针对以上两点,系统地谈一谈究竟什么样的问题可以用动态规划来解。

    一、动态规划是一种思想

    动态规划算法,这种叫法我想你应该经常听说。嗯,从道理上讲这么叫我觉得也没错,首先动态规划它不是数据结构,这一点毋庸置疑,并且严格意义上来说它就是一种算法。但更加准确或者更加贴切的提法应该是说动态规划是一种思想。那算法和思想又有什么区别呢?

    一般来说,我们都会把算法和数据结构放一起来讲,这是因为它们之间密切相关,而算法也往往是在特定数据结构的基础之上对解题方案的一种严谨的总结。

    比如说,在一个乱序数组的基础上进行排序,这里的数据结构指的是什么呢?很显然是数组,而算法则是所谓的排序。至于排序算法,你可以考虑使用简单的冒泡排序或效率更高的快速排序方法等等来解决问题。

    没错,你应该也感觉到了,算法是一种简单的经验总结和套路。那什么是思想呢?相较于算法,思想更多的是指导你我来解决问题。

    比如说,在解决一个复杂问题的时候,我们可以先将问题简化ÿ

    展开全文
  • 本文收录了在时间效率上动态规划的三大优化:四边形不等式,斜率优化,单调队列优化。另外,也收录了解决NP问题小规模求解中,优于搜索的状态压缩动态规划。 关键词:动态规划优化,四边形不等式,斜率优化,单调...
  • 说实话,我觉得很难,特别是对于初学者来说,我当时入门动态规划时候,是看 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)。

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

    展开全文
  • 没错,它就是我们今天的主角——动态规划。 初识 我们先来回顾一下带备忘录的递归——将每次计算的结果储存起来,下次若再次遇到,则只需直接从记忆表中提取即可。这是一种空间换取时间的方法,显然,这是十分正确...

    灵感

    递归能够解决的问题,说白了就是能分解为许多个相同类型的规模更小的子问题的问题,其实就是一种分治思想,递归只是其中的一种实现手段而已。而当存在着大量重复子问题的时候,单纯的递归效率确实太低了,所以这种情况下,若仍想使用递归,就必须使用带备忘录的递归。那么,是否存在一种非递归,也就是迭代的实现方法呢?
    没错,它就是我们今天的主角——动态规划。

    初识

    我们先来回顾一下带备忘录的递归——将每次计算的结果储存起来,下次若再次遇到,则只需直接从记忆表中提取即可。这是一种用空间换取时间的方法,显然,这是十分正确有效的方法,毕竟,空间不足尚可弥补,时间不足那就真的没办法了。
    不难发现,既然要将结果储存在一张表内,那么是不是可以采用迭代的方式直接将这张表的元素全部算出来呢?答案显然是肯定的,而这样直接利用迭代的方式将整张表全部算出来的方式,就是动态规划。

    实现

    仍然利用斐波那契数列的例子,动态规划的实现如下:

    int F(int n) {
    	vector<int> dp(n + 1, 1);	//创建dp数组用来储存计算结果
    	for (int i = 3; i <= n; ++i) {	//从3一直算到n,并储存在表内
    		dp[i] = dp[i - 1] + dp[i - 2];	//根据递推关系(在动态规划中称为状态转移方程)计算表中当前值
    	}
    	return dp[n];	//从表中取得所需要的值并返回
    }
    

    一般来说实现动态规划之前需要如下准备:

    1.确认状态
    2.确认状态转移方程

    什么是状态?
    状态就是指dp[n]意味着什么,比如这里的dp[n]就意味着斐波那契数列中的第n项。
    什么是状态转移方程?
    与递推关系式类似,就是指如何用之前表中计算得到的状态来得到当前状态(状态转移)的关系式。
    如这里就是dp[n] = dp[n - 1] + dp[n - 2];

    深入

    我们之前说过,动态规划是用空间来换取时间,但事实上最终真正用到的往往只是表中的某个状态而已(往往是尾部),而且,表中所有状态最终都是由最基本的两个状态决定的。那么,是否能压缩空间,让空间复杂度也进一步缩小呢?
    一般情况下,可以采用以下这种方式:

    int F(int n) {
    	int pre1 = 1, pre2 = 1, cur;	//首先用pre1和pre2记录所有基态,并用cur记录当前状态
    	for (int i = 3; i <= n; ++i) {
    		cur = pre1 + pre2;	//利用状态转移方程与之前计算得到的状态算出当前状态
    		pre1 = pre2;	//更新状态pre1,这里pre1是cur前距离cur为2的状态
    		pre2 = cur;	//更新状态pre2,这里pre2是cur前一个状态
    	}
    	return n < 3 ? 1 : cur;	//返回当前状态,也就是最终状态,但若所求状态即为基态,则可直接返回基态的值即pre1或pre2,当然本题也可以取巧,设cur初值为1,直接返回cur
    }
    

    显然,空间复杂度由原来的O(n)变为了O(1)。

    展开全文
  • 活动安排问题的动态规划、贪心算法和树搜索算法求解。 比如有一个多媒体教室,现在有四个待举办活动A、B、C、D。A是8:00到10:00举行,简单记为[8, 10];B是[12, 14];C是[15, 17];D是[11, 19]。为了让尽可能多的...
  • 课程的随堂作业,C语言的,dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 动态规划-多边形游戏

    2018-11-08 11:52:58
    与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的.若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次.如果我们能够保存已解决的子问题的答案,而...
  • 递归与动态规划

    2021-12-12 10:11:13
    动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。 动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。 1、线性动规:拦截导弹,合唱队形...
  • 一、动态规划的定义以及术语 1.定义:将一个问题分解为子问题递归求解,并且将中间结果保存以避免重复计算的办法,就叫做“动态规划” 2.阶段:把求解问题的过程恰当...6.使用动态规划时满足的性质:(1)最优子结构
  • 关于动态规划之前刷过一些相关的题,但都是类似背包问题、爬楼梯问题,那时候觉得这个算法挺简单。直到最近看jieba的源码,其中两次使用到...觉得理解了一个问题为什么能够使用动态规划?拿到一个问题时,如何判...
  • 设有n种不同面值的硬币,第i种硬币的币值是vk(其中v1=1),重量是wi,i=12...n且现在购买总价值为y的某些商品,需要这些硬币付款,如果每种钱币使用的个数不限,问如何选择付款的方法使得付出钱币的总重量最轻?...
  • 前言 相比于其他算法思想,动态规划的难度较大。同时,动态规划也是最强力的一种算法思想。有很多问题,用贪婪思想或者分而治之无法简洁而高效的解决,但是用动态规划就可以。 动态规划的基础为最优原理。 ...
  • 造成规划时间的增加,D*算法的核心思想是先dijkstra或A*从目标点向初始点进行反向搜索,然后机器人从起点向目标点移动,当遇到动态障碍物时,只进行局部的更改即可,效率明显提高。本仿真基于matlab进行D*算法的...
  • 如果大家对这个生僻的术语不理解的话,那就先听小编给大家说个现实生活中的实际案例吧,虽然现在手机是相当的便捷,还可以付款,但是最初的时候,我们经常会使用硬币,其中,我们如果遇到手中有很多五毛或者1块钱...
  • 谈到动态规划,首先说明关于动态规划的几个术语:阶段,状态,无后效性,决策,策略,状态转移方程 阶段:把求解问题的过程恰当地拆分成若干个相互联系的阶段,以便于求解。 状态:每一个阶段开始的时候处于的处境...
  • 解题思路: 这道题其实最传统的做法就是...为了解决该问题,我们可以使用动态规划,将每次前两数之和存起来,便于下次直接使用,这样子,我们就把一个栈溢出的问题,变为了单纯的数学加法,大大减少了内存的压力。 ...
  • 为了获得非线性离散时间系统的最优控制策略, 基于自适应动态规划的原理, 提出了一种带误差限的自适 应动态规划方法. 对于一个任意的状态, 一个有限长度的控制序列近似最优控制序列, 使性能指标与最优性能指标...
  • 动态规划(Dynamic programming,简称DP)很多人都觉得是比较难以理解和掌握的一种算法,为了应付面试更多的时候程序员会选择直接死记硬背斐波那楔数列或者背包问题的源码,其实只要认真学习、彻底理解,动态规划并...
  • 最大子段和问题,可参考《算法设计与分析》讲义中关于用动态规划策略求解最大子段和问题的思想设计动态规划算法。本算法用户需要输入元素个数n,及n个整数。程序应该给出良好的用户界面,输出最大子段相关信息,包括...
  • leetcode找零钱问题动态规划 LeetCode 动态规划 一般解法 注意: 递归算法为从高到底, 动态规划算法为从底到高! 找到转移方程 题目 No.124 二叉树中的最大路径和 No.322 零钱兑换 回溯算法 一般解法 注意: 感觉有点...
  • 首先,读者需要知道,动态规划实质上是一种思想,并不是以中具体的算法,面对某些问题的啥时候,我们可以利用动态规划这个思想将问题转化,从而达到解决问题的地步。 补充一点:动态规划简称dp(全称dynamic ...
  • 什么动态规划动态规划的意义是什么

    千次阅读 多人点赞 2019-03-13 23:25:12
    以往见过许多教材,对动态规划(DP)的引入属于“奉天承运,皇帝诏曰”式:不给出一点引入,见面即拿出一大堆公式吓人;学生则死啃书本,然后突然顿悟。针对入门者的教材不应该是这样的。 现在,我们试着自己来一...
  • 详解动态规划算法

    千次阅读 多人点赞 2020-04-09 07:59:47
    那么怎么判断题目是否可以用动态规划求解呢,其实也很简单,当问题的定义是求最值问题,且问题可以采用递归的方式,并且递归的过程中有大量重复子问题的时候,基本可以断定问题可以用动态规划求解,于是我们得出了...
  • 分治,动态规划,备忘录搞不清,遇到问题不知道应该用什么样的方法合适? 分治:分治算法对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互独立且与原问题相同的子问题(不包含公共的子问题...
  • 使用自适应动态规划的一类具有多个时滞的线性离散时间系统的无模型最优控制设计
  • 分析最优解结构的基础上,Java语言给出...全文分为四个部分,首先讨论 了动态规划时间效率优化的可行性和必要性,接着给出了动态规划时间复杂度的决定因素,然后分别阐述了对各个决定因 素的优化方法,最后总结全文。
  • 2、使用动态规划技术的必要条件:满足优化原则 优化原则: 一个最优决策序列的任何子序列本身一定的是相对于子序列的初始和结束状态的最优决策序列; 最优解不满足优化原则的问题不能使用动态规划算法; 3、动态...
  • 动态规划入门篇

    千次阅读 多人点赞 2022-03-18 16:50:36
    动态规划和递归非常的相似,都是通过组合子问题的解来求解原问题,且一般递归的问题都可以转化为动态规划,咱们举个简单的例子斐波那契数列。 第i个斐波那契数列值F[i]=F[i-1]+F[i-2],如果我们想知道F[n],...
  • C++动态规划详解

    千次阅读 2021-09-11 18:30:59
    在动态规划中,为了寻找一个问题的最优解(即最优决策过程),将整个问题划分成若干个相应的阶段,并每个阶段都根据先前所作出的决策作出当前阶段最优决策,进而得出整个问题的最优解。即记住已知问题的答案,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 217,116
精华内容 86,846
关键字:

在什么时候使用动态规划

友情链接: ucGUI.rar