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

    千次阅读 2020-04-06 21:55:23
    动态规划解题步骤? 判断原问题是否能用递归解决 分析递归过程中是否存在重复子问题 采用备忘录法记录重复子问题解(剪枝) 改用自底向上地推(动态规划) 我们以编辑距离为例来分析上面步骤: 给你两个...

    动态规划解题步骤?

    • 判断原问题是否可递归求解
    • 分析递归过程中是否存在重复子问题
    • 采用备忘录法记录重复子问题的解(剪枝)
    • 改用自底向上的递推(动态规划)

    我们以编辑距离为例来分析上面的步骤:

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

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

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

    示例 1:

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

    分析:

    1、当第一个字符串的第一个字符和第二个字符串的第一个字符相同时,对结果没有增益效果。
    2、当第一个字符串的第一个字符和第二字符串的第一个字符不相同时,有三种情况

    a.插入一个字符
    b.删除一个字符
    c.替换一个字符

    递归加备忘录:递归加备忘录
    动态规划:
    在这里插入图片描述

    展开全文
  • 图解动态规划的解题步骤

    千次阅读 2020-04-02 20:36:44
    如果你对于动态规划还不是很了解,...动态规划的的四个解题步骤是: 定义子问题 写出子问题的递推关系 确定 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 。

    展开全文
  • 动态规划问题一般形式就是求最值,动态规划有三个要素 重叠子问题。通过备忘录和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)相加。
    在这里插入图片描述

    动态规划详细案例分析

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

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

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

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

    动态规划常见类型

    展开全文
  • 选择:在排好序进行选择时,通常会选择满足可行解中最小解,将更大可行解保留用于解决之后选择(既做到了局部最优,又有保留将更有利的的解留到了后续选择中,做到了贪心) 辅助:常利用数组记录进行局部...

    1.贪心算法

    • 贪心点:贪心算法即贪心选择策略(判断怎么选择才能做到每一次选择达到局部最优,即找到贪心点)
    • 排序:贪心问题一般都涉及到排序(Comparable、Comparator),通常可能会涉及到两个选择属性自定义排序
    • 选择:在排好序进行选择时,通常会选择满足可行解中最小的解,将更大的可行解保留用于解决之后的选择(既做到了局部最优,又有保留的将更有利的的解留到了后续选择中,做到了贪心)
    • 辅助:常利用数组记录进行局部选择时满足可行解的个数或顺序位置

    2.动态规划

    • 1.动态规划算法一般都有下面两种实现方式,前者称为递归版本,后者称为迭代版本,且两个版本是可以相互转换的。
      - 1.直接自顶向下实现递归式,并将中间结果保存,这叫备忘录法;
      - 2.按照递归式自底向上地迭代,将结果保存在某个数据结构中求解。
    • 2.一般求解思路
      1.原问题分解为子问题
    • 把原问题分解为若干个子问题,子问题和原问题地形式相同或类似,只是规模变小了。当子问题都解决时,原问题也就解决了。
    • 子问题一旦求出就立即保存(重叠子问题性质),所以每个问题只需被求解一次
      2.确定状态
    • 在动态规划问题中,常常将和子问题相关的各个变量的一组取值称之为一个“状态”,经常碰到的情况是,k个整形变量能构成一种状态(如数字三角形问题中的行号和列号)。如果k个整形变量取值范围分别是N1、N2、N3…Nk,那么,我们经常会用一个k维数组 array[N1][N2][N3]…[Nk]来存储各个状态的值,而此值就是当前状态下子问题的解; 并且,此值未必是一个整形或浮点数,可能需要一个结构才能表示的,那么array数组就是一个结构数组。
      3.确定一些初始状态(边界状态)的值
    • 动态规划问题中经常采用递推实现,可以初始化最底层状态下的值。
      4.确定状态转移方程
    • 定义出什么是“状态”,以及在该“状态”下的值后,就要找出不同状态之下如何迁移——即如何从一个或多个“值”(已知的状态),求解出另一个“状态”下的值(“人人为我” 递推型) 状态的迁移可以用递推公式表示,此递推公式被称为:“状态转移方程”

    3.贪心与动规区别联系

    • 1.概念

    • 贪心算法
      基本思想:贪心算法并不从整体最优上加以考虑,它所做的选择只是在某种意义上的局部最优解。
      基本要素:最优子结构性质贪心选择性质

    • 动态规划
      基本思想:将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
      基本要素:最优子结构性质重叠子问题性质无后效性
      无后效性: 当前若干个值一旦确定后,此后过程的演变只与这若干个状态的值有关,和之前采用那种手段或经过哪条路径演变到当前若干个状态无关。

    • 区别联系

    • 共同点:两者都具有最优子结构性质

    • 不同点:
      1.动态规划算法中,每步所做的选择往往依赖于相关子问题的解,因而只有在解出相关子问题时才能做出选择。
      贪心算法,仅在当前状态下做出最好选择,即局部最优选择,然后再去解做出这个选择后产生的相应的子问题,对后续子问题继续选择从而达到全局最优。
      2.动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常自顶向下的方式进行。

    展开全文
  • 动态规划解题套路 文章目录动态规划解题套路与贪心区别动规套路动规debug 与贪心区别 借鉴【代码随想录】大佬一句话,动态规划就是由前一个状态推导出来;贪心是局部选取最优,与前一状态无关。 动规套路 确定...
  • 目录1 题目场景2 解题步骤3 案例分析 1 题目场景 1 计数 有多少种方式走到右下角; 有多少种方法选出k个数使得和为sum; 2 求最值 从左上角走到右下角路径最大数字和; 最长上升子序列长度 3 求存在性 取石子...
  • 动态规划解题思路

    2020-11-30 16:57:59
    动态规划 一直以来都没有好好的了解动态规划问题,因为现在很多的笔试题中都会涉及动态规划的问题,所以通过学习动态规划来记录一下学习的笔记。...动态规划的解题步骤 1. 确定状态: 最后一步 关键
  • 动态规划类问题解题步骤 --附例题(小偷问题)动态规划基本思想适用情况优点解题步骤实例分析问题解题步骤 动态规划 基本思想 动态规划背后基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分...
  • 点击关注上方“五分钟学算法”,设为“置顶或星标”,第一时间送达干货。转自面向大象编程本期例题:LeetCode 198. House Robber 打家劫舍(Easy)你是一个专业小偷...
  • 动态规划(英语:Dynamic programming,简称 DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用,通过把原问题分解为相对简单子问题方式求解复杂问题方法。 动态规划常常适用于有重叠子...
  • 解题的前提就是确定题中状态是什么,一般情况下,动态规划需要开一个数组,数据每个元素f(i)或者f(i)(j)代表就是状态。 确定状态需要通过两个思考:最后一步和子问题,找出原问题和子问题中变化变量,这个...
  • 二、分析:动态规划解题步骤包含四个部分 (1)部分一:确定状态 (1.1)最后一步 (1.2)子问题 (1.3)递归解法 (2)部分二:转移方程 (3)部分三:初始条件和边界情况 (4)第四...
  • 第一次觉得动态规划题目这么清晰... 动态规划的解题步骤: 确定状态 最后一步:最优策略挪动的最后一步 子问题:比原问题规模小 转移方程 初始条件和边界情况 初始条件通常是转移方程计算不出来的所以需..
  • 动态规划解题步骤 1.定义子问题: 什么可以算得上有子问题,可以用动态规划解决问题呢?例如在打家劫舍算法题中,问题可以被拆分为各个子问题,子问题是打劫前k家能得到最大金额。假设一共有 n 个房子话,就...
  • 一个机器人位于一个m*n网络左上角,机器人每次只能向左向右移动一步。机器人试图达到网格右下角,总共有多少条不同路径。 首先要确定状态 确定状态 最后一步 这里最后一步是走到网格右下角,那么定义走到...
  • 说明:该文章所直接使用的动态规划解题步骤来自上述课程,不再具体讲解,直接使用。 1:把原问题化为子问题。首先考虑是----“求序列前i个元素最长递增子序列”,即可以定义F(i)=x;x是当前状态值。...
  • 动态规划算法解题思路

    千次阅读 2020-09-14 09:42:55
    在做动态规划类题目时最大感觉就是能够分析出这道题目需要用动态规划算法来解,却没有办法构建出解题步骤,看到别人分析时候又感觉代码很简单但是自己却想不出。 其实这还是没有理解到动态规划算法基本思想。 ...
  • 动态规划解题的一般模式

    千次阅读 2013-03-14 14:18:24
    动态规划的设计都有着一定的模式,一般要经历以下几个步骤。 ┌───┐┌───┐┌───┐ 初始状态→│决策1│→│决策2│→…→│决策n│→结束状态 └───┘
  • 则问题就无法求解; b、确定状态和状态变量:将问题发展到各个阶段时所处于各种客观情况用不同状态表示出来。...但事实上常常是反过来,根据相邻两个阶段状态之间关系来确定决策方法...
  • 目录1动态规划思想2适用场景3例题分析3.1示例1:42.接雨水 1动态规划思想 2适用场景 3例题分析 3.1示例1:42.接雨水 题目描述 给定 n 个非负整数表示每个宽度为 1 柱子高度图,计算按此排列柱子,下雨之后能接...
  • 每间房内都藏有一定现金,影响你偷窃唯一制约因素就是相邻房屋装有相互连通防盗系统,如果两间相邻房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额非负整数数组,计算你 不...
  • 动态规划应用于子问题重叠情况,即不同子问题具有公共子子问题;动态规划算法对每个子子问题只求解一次;动态规划通常用来求解最优化问题。 解题步骤: 判题题意是否为找出一个问题最优解 将原问题分解为子...
  • Java数据结构和算法——动态规划做题步骤详细总结

    千次阅读 多人点赞 2020-07-11 18:19:48
    文章目录动态规划题目类型动态规划解题步骤动态规划实例讲解硬币问题机器人路径问题青蛙跳石头问题 动态规划题目类型 1、计数: 有多少种方式走到右下角 有多少种方法选出k个数使得和为Sum 2、求最大最小值: 从左上...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 323
精华内容 129
关键字:

动态规划的解题步骤