精华内容
下载资源
问答
  • 图解动态规划的解题四步骤

    千次阅读 2020-04-02 20:36:44
    本文会以 House Robber 题目为例子,讲解动态规划题目的四个基本步骤动态规划的的四个解题步骤是: 定义子问题 写出子问题的递推关系 确定 DP 数组的计算顺序 空间优化(可选) 下面我们一步一步地进行讲解。 ...

    如果你对于动态规划还不是很了解,或者没怎么做过动态规划的题目的话,那么 House Robber (小偷问题)这道题是一个非常好的入门题目。本文会以 House Robber 题目为例子,讲解动态规划题目的四个基本步骤。

    动态规划的的四个解题步骤是:

    • 定义子问题
    • 写出子问题的递推关系
    • 确定 DP 数组的计算顺序
    • 空间优化(可选)

    下面我们一步一步地进行讲解。

    步骤一:定义子问题

    稍微接触过一点动态规划的朋友都知道动态规划有一个“子问题”的定义。什么是子问题?子问题是和原问题相似,但规模较小的问题。例如这道小偷问题,原问题是“从全部房子中能偷到的最大金额”,将问题的规模缩小,子问题就是“从 k 个房子中能偷到的最大金额”,用 f(k) 表示。

    在这里插入图片描述

    可以看到,子问题是参数化的,我们定义的子问题中有参数 kk。假设一共有 nn 个房子的话,就一共有 nn 个子问题。动态规划实际上就是通过求这一堆子问题的解,来求出原问题的解。这要求子问题需要具备两个性质:

    • 原问题要能由子问题表示。例如这道小偷问题中,k=nk=n 时实际上就是原问题。否则,解了半天子问题还是解不出原问题,那子问题岂不是白解了。
    • 一个子问题的解要能通过其他子问题的解求出。例如这道小偷问题中,f(k)f(k) 可以由 f(k-1)f(k−1) 和 f(k-2)f(k−2) 求出,具体原理后面会解释。这个性质就是教科书中所说的“最优子结构”。如果定义不出这样的子问题,那么这道题实际上没法用动态规划解。

    小偷问题由于比较简单,定义子问题实际上是很直观的。一些比较难的动态规划题目可能需要一些定义子问题的技巧。

    步骤二:写出子问题的递推关系

    这一步是求解动态规划问题最关键的一步。然而,这一步也是最无法在代码中体现出来的一步。在做题的时候,最好把这一步的思路用注释的形式写下来。做动态规划题目不要求快,而要确保无误。否则,写代码五分钟,找 bug 半小时,岂不美哉?

    我们来分析一下这道小偷问题的递推关系:

    假设一共有 nn 个房子,每个房子的金额分别是 H0, H1, …,Hn-1,子问题 f(k)f(k) 表示从前 k 个房子(即 H0, H1,…Hk-1,中能偷到的最大金额。那么,偷 k 个房子有两种偷法:

    在这里插入图片描述

    k 个房子中最后一个房子是 Hk-1。如果不偷这个房子,那么问题就变成在前 k-1个房子中偷到最大的金额,也就是子问题 f(k-1)。如果偷这个房子,那么前一个房子 Hk-2显然不能偷,其他房子不受影响。那么问题就变成在前 k-2 个房子中偷到的最大的金额。两种情况中,选择金额较大的一种结果。

    f(k) = max{f(k-1), Hk-1 + f(k-2)}

    在写递推关系的时候,要注意写上 k=0k=0 和 k=1k=1 的基本情况:

    • 当 k=0 时,没有房子,所以 f(0) =0。
    • 当 k=1 时,只有一个房子,偷这个房子即可,所以 f(1) = H0

    这样才能构成完整的递推关系,后面写代码也不容易在边界条件上出错。

    步骤三:确定 DP 数组的计算顺序

    在确定了子问题的递推关系之后,下一步就是依次计算出这些子问题了。在很多教程中都会写,动态规划有两种计算顺序,一种是自顶向下的、使用备忘录的递归方法,一种是自底向上的、使用 dp 数组的循环方法。不过在 普通的动态规划题目中,99% 的情况我们都不需要用到备忘录方法,所以我们最好坚持用自底向上的 dp 数组。

    DP 数组也可以叫”子问题数组”,因为 DP 数组中的每一个元素都对应一个子问题。如下图所示,dp[k] 对应子问题 f(k),即偷前 kk 间房子的最大金额。

    在这里插入图片描述

    那么,只要搞清楚了子问题的计算顺序,就可以确定 DP 数组的计算顺序。对于小偷问题,我们分析子问题的依赖关系,发现每个 f(k) 依赖 f(k-1) 和 f(k−2)。也就是说,dp[k] 依赖 dp[k-1] 和 dp[k-2],如下图所示。

    在这里插入图片描述

    那么,既然 DP 数组中的依赖关系都是向右指的,DP 数组的计算顺序就是从左向右。这样我们可以保证,计算一个子问题的时候,它所依赖的那些子问题已经计算出来了。

    确定了 DP 数组的计算顺序之后,我们就可以写出题解代码了:

    Java:

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // 子问题:
        // f(k) = 偷 [0..k) 房间中的最大金额
    
        // f(0) = 0
        // f(1) = nums[0]
        // f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }
    
        int N = nums.length;
        int[] dp = new int[N+1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int k = 2; k <= N; k++) {
            dp[k] = Math.max(dp[k-1], nums[k-1] + dp[k-2]);
        }
        return dp[N];
    }
    

    步骤四:空间优化

    空间优化是动态规划问题的进阶内容了。对于初学者来说,可以不掌握这部分内容。

    空间优化的基本原理是,很多时候我们并不需要始终持有全部的 DP 数组。对于小偷问题,我们发现,最后一步计算 f(n) 的时候,实际上只用到了 f(n-1) 和 f(n-2) 的结果。n-3 之前的子问题,实际上早就已经用不到了。那么,我们可以只用两个变量保存两个子问题的结果,就可以依次计算出所有的子问题。下面的动图比较了空间优化前和优化后的对比关系:

    在这里插入图片描述

    这样一来,空间复杂度也从 O(n)O(n) 降到了 O(1)O(1)。优化后的代码如下所示:

    Java:

    public int rob(int[] nums) {
        int prev = 0;
        int curr = 0;
    
        // 每次循环,计算“偷到当前房子为止的最大金额”
        for (int i : nums) {
            // 循环开始时,curr 表示 dp[k-1],prev 表示 dp[k-2]
            // dp[k] = max{ dp[k-1], dp[k-2] + i }
            int temp = Math.max(curr, prev + i);
            prev = curr;
            curr = temp;
            // 循环结束时,curr 表示 dp[k],prev 表示 dp[k-1]
        }
    
        return curr;
    }
    

    题目 打家劫舍

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

    给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

    示例

    示例 1:

    输入: [1,2,3,1]
    输出: 4
    解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
    偷窃到的最高金额 = 1 + 3 = 4 。

    示例 2:

    输入: [2,7,9,3,1]
    输出: 12
    解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
    偷窃到的最高金额 = 2 + 9 + 1 = 12 。

    展开全文
  • 动态规划方法步骤

    2014-10-19 19:38:11
    动态规划方法的四个步骤: 1.刻画一个最优解的结构特征。 2.


    动态规划方法的四个步骤:

    1.刻画一个最优解的结构特征。

    2.递归定义最优解的值。

    3.计算最优解的值,通常采用自底向上的方法。

    4.利用计算出的信息构造一个最优解。

    (算法导论 中文版 第三版 P212)

    展开全文
  • 动态规划(DP)的四个步骤定义元素的含义找出数组元素之间的关系初始化数组DONE 定义元素的含义 常常是一维数组或者二维数组 找出数组元素之间的关系 初始化数组 DONE ...

    定义元素的含义

    常常是一维数组或者二维数组

    找出数组元素之间的关系

    初始化数组

    DONE

    展开全文
  • 动态规划问题一般形式就是求最值,动态规划有三要素 重叠子问题。通过备忘录和DP数组来优化穷举过程 最优子结构。通过子问题的最值得出原问题的最值 状态转移方程。如何正确的穷举的关键,可以通过步法来确定...

    题目特点

    1. 计数
      • 有多少种方式走到右下角
      • 有多少种方式选出K个数使得和是Sum
    2. 最值
      • 从左上角走到右下角路径的最大值
      • 最长上升子序列的长度
    3. 存在性
      • 能不能选出K个数和是Sum
      • 取石子游戏,先手是否必胜

    四要素

    • 确定状态。最后一步和子问题
    • 状态转移方程。找出重叠子问题,列出状态转移方程。
    • 初始条件和边界情况
    • 计算顺序

    下面将从两个例子来展开介绍,通过斐波那契数列让你明白什么是重叠子问题,通过凑零钱问题分析如何列出状态转移方程。

    斐波那契数列

    暴力法

    public int fib(int N) {
    
            if (N == 1 || N == 2) {
                return 1;
            }
    
            return fib(N - 1) + fib(N - 2);
    
    }
    

    以F(10) 为例,发现暴力解法中出现了很多的重复计算,比如F(8)计算了两次。
    在这里插入图片描述

    备忘录优化

    耗时主要是重复计算问题,可以通过数组或者哈希表来存储计算结果,充当备忘录。

      //map也可以初始化为一个N+1的数组
       Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
        public int fib(int N) {
            if (N<1){
                return 0;
            }
            if (map.get(N) != null) {
                return map.get(N);
            }
    
            if (N == 1|| N==2) {
                return 1;
            }
    
            int result = fib(N - 1) + fib(N - 2);
    
            map.put(N, result);
    
            return result;
    
    }
    

    DP数组

     public int fib(int n){
            if(n<1){
                return 0;
            }
            if(n==1||n==2){
                return 1;
            }
            int[] dp=new int[n+1];
    
            dp[1]=dp[2]=1;
    
            for (int i = 3; i <= n; i++) {
                dp[i]=dp[i-1]+dp[i-2];
            }
            return dp[n];
    }
    

    状态转移方程,状态是f(n),把f(n)状态转移到f(n-1)和f(n-2)相加。
    在这里插入图片描述

    动态规划详细案例分析

    最值类-凑零钱问题(点击查看详细)

    计数类-不同路径问题(点击查看详细)

    计数类-最长递增子序列(点击查看详细)

    存在类-跳跃游戏问题(点击查看详细)

    动态规划常见类型

    展开全文
  • 一般来说,解动态规划的时候需要开一数组f,数组的每元素f[i]、f[i][j]意味着什么,类似于数学题中X、Y、Z代表着什么 【确定状态】需要两意识 - 最后一步 - 子问题 比如在这道题中: 【关键点】 1、我们现在...
  • 点击关注上方“五分钟学算法”,设为“置顶或星标”,第一时间送达干货。转自面向大象编程本期例题:LeetCode 198. House Robber 打家劫舍(Easy)你是一专业的小偷...
  • 并且动态规划这种通过空间换取时间的算法思想在实际的工作中也会被频繁用到,这篇文章的目的主要是解释清楚什么是动态规划,还有就是面对一道动态规划问题,一般的思考步骤以及其中的注意事项等等,最后通过几道题目...
  • 动态规划

    2020-08-26 20:05:50
    动态规划的基本思想 将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。...设计动态规划法的步骤 1.找出最
  • 动态规划

    2019-10-28 20:54:10
    文章目录一、 什么是动态规划二、动态规划的基本思想三、动态规划的问题特征、设计动态规划步骤五、最长公共子序列六、0-1背包问题(不能分割) 一、 什么是动态规划 动态规划(Dynamic Programming)是运筹学的...
  • 二、分析:动态规划解题步骤包含四个部分 (1)部分一:确定状态 (1.1)最后一步 (1.2)子问题 (1.3)递归解法 (2)部分二:转移方程 (3)部分三:初始条件和边界情况 (4)第四...
  • 文章目录动态规划(Dynamic Programming)浅学题目特点:1、选择硬币组合问题:(Coin Change)动态规划四个核心步骤:一、确定状态二、转移方程三、初始条件和边界情况四、计算顺序小结:编程代码:(Java)2、...
  • 你是一专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一代表每...
  • 动态规划

    2020-08-22 21:16:22
    第一步:确定动态规划状态第二步:写出一好的状态转移方程第三步:考虑初始条件第步:考虑输出状态第五步:考虑对时间,空间复杂度的优化(Bonus)Leetcode 674.最长连续递增序列第一步:确定动态规划状态第二步...
  • 动态规划

    2020-03-29 17:24:37
    一、具有的特征 1.问题具有多阶段性决策的特征 2.每一阶段有相应的“状态变量”。 3.不同决策导致下一阶段不同的状态 4.多阶段的最优解的递归,子问题与原问题有同结构。 ...1.是否具有动态规...
  • 动态规划理论

    2019-08-12 20:54:51
    前面一篇文件使用几个简单的程序介绍了回溯和动态规划之前的区别,但是没有说出动态规划本质的特色,像贪心算法三个步骤一样,本篇文章将主要围绕解题思路来讲,目的是让大家明白什么样的问题可以使用动态规划算法,...
  • 蓝桥杯 动态规划

    2021-05-08 22:35:12
    动态规划的的四个解题步骤是: 定义子问题 写出子问题的递推关系 确定 DP 数组的计算顺序 空间优化(可选) 动态规划本质是递推,核心是找到状态转移的方式,写出dp方程 经典题解 打家劫舍 你是一个专业的...
  • 动态规划初级

    2020-11-21 17:19:52
    *一般解决动态规划问题,分为四个步骤,分别是 ①问题拆解,找到问题之间的具体联系 ②状态定义,例如,dp[i]表示当前第i步的最优解 ③递推方程推导,找出状态方程,dp[i]与前面最优解之间的关系,如dp[i]=dp[i-1]+...
  • 简单动态规划

    2020-03-14 10:14:13
    动态规划看似很难,实则有规律可循,做动态规划题目可将其化为以下四个步骤。 一、确定状态(开一个一维或者二维数组): (一):寻找最后一步(找到最优策略的最后一步,然后去掉最后一步,分析之前的步骤) ...
  • 在基础部分,我们介绍了动态规划法的两个重点和实现动态规划法的四个步骤,在第 4 部分动态规划中,我们将介绍一系列动态规划类的算法例子,这些例子覆盖一维动态规划、串模型的动态规划、区间模型动态规划以及状态...
  • 动态规划小结

    2020-03-29 16:00:14
    动态规划看似很难,实则有规律可循,做动态规划题目可将其化为以下四个步骤,需要掌握这种思想,然后做到举一反三。 简单来说动态规划可以分成以下几个步骤 一、确定状态(开一个一维或者二维数组): (一):寻找...
  • 实验要求:分别用伪代码或流程图或步骤分析图描述利用动态规划、贪心策略、回溯法的算法解决方案,再用程序实现,计算时间复杂度,记录最终测试数据和测试结果,运行时间。 旅行商问题 问题描述:给定一的整数矩阵...
  • 动态规划算法的一般步骤 1.找出最优解的性质,并刻画其结构特征; 2.递归地定义最优值; 3.以自底向上的方式计算出最优值; 根据计算最优值时得到的信息,构造最优解 下面用一例子来说明。 矩阵连乘...
  • 求两字符串的最长公共子序列——程序设计艺术与方法实验 动态规划算法的实现 (1) 求两字符串的最长公共子序列。 - 151 - X 的一个子序列是相应于 X 下标序列{1, 2, …, m}的一个子序列,求解两序列的所有子...
  • 并且动态规划这种通过空间换取时间的算法思想在实际的工作中也会被频繁用到,这篇文章的目的主要是解释清楚什么是动态规划,还有就是面对一道动态规划问题,一般的思考步骤以及其中的注意事项等等,最后通过几道题目...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 236
精华内容 94
关键字:

动态规划四个步骤