-
动态规划解题步骤
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-07-14 10:58:20动态规划问题一般形式就是求最值,动态规划有三个要素 重叠子问题。通过备忘录和DP数组来优化穷举过程 最优子结构。通过子问题的最值得出原问题的最值 状态转移方程。如何正确的穷举的关键,可以通过四步法来确定...文章目录
题目特点
- 计数
- 有多少种方式走到右下角
- 有多少种方式选出K个数使得和是Sum
- 最值
- 从左上角走到右下角路径的最大值
- 最长上升子序列的长度
- 存在性
- 能不能选出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)相加。
动态规划详细案例分析
最值类-凑零钱问题(点击查看详细)
计数类-不同路径问题(点击查看详细)
计数类-最长递增子序列(点击查看详细)
存在类-跳跃游戏问题(点击查看详细)
动态规划常见类型
- 计数
-
关于动态规划解题步骤和两个重要性质的理解---以最长递增子序列为例
2017-03-02 16:58:30说明:该文章所直接使用的动态规划解题步骤来自上述的课程,不再具体讲解,直接使用。 1:把原问题化为子问题。首先考虑的是----“求序列前i个元素的最长递增子序列”,即可以定义F(i)=x;x是当前状态的值。...首先要感谢自己幸运地看到了慕课网上,北大老师的程序设计与算法课。讲得真心不错,推荐一看。说明:该文章所直接使用的动态规划解题步骤来自上述的课程,不再具体讲解,直接使用。看另外,该文章以步骤的第一步为主,重点讲解无后效性,后面三步不再赘述。1:把原问题化为子问题。首先考虑的是----“求序列前i个元素的最长递增子序列”,即可以定义F(i)=x;x是当前状态的值。进一步分析,虽然,状态的值只有一个,但是到达这个状态的途径有很多,进一步想F(i+1),如果这些不同途径中的某个途径(序列)的最后一个元素比ai+1小,那么F(i+1)就会是更长的子序列;反之,如果不比ai+1小,F(i+1)就不一样了。这样,F(i+1)的值不仅与当前状态的值(x)有关了,也就不满足无后效性。补充:(无后效性定义)当前的若干个状态的值一旦确定,则此后过程的演变就只和这若干个状态的值有关,和之前采取哪种手段或经过哪条路径演变到当前这若干个状态无关。所以,子问题这么划分是不适合用动态规划的。我们接下来换个子问题的设法。 “子问题为以元素ai结尾的最长递增子序列”,即F(ai)=x;这样就保证了,在我们求出了所有的解以后,找出最大的那个就可以了。为什么满足了呢?我们这样想,我们最后会求出所有元素的F(ai),这些值可能相等可能不等,但不管如何,最后我们要把这些值求最大值,根本不用管到达max(F[ai])经过了那些值,所以只与状态的值有关。2:确定状态 即每个元素的下标k,因为状态只包含一个变量,所以存储状态值的数组是一维的。即maxvalue【n】;3:确定一些初始状态的值,在这里我们把初始状态都初始化为1,即以自身结尾的最低要求是一个长度。4:状态转移方程 网上一搜就看到,不再赘述。 -
动态规划(二)——含解题步骤
2020-10-19 16:08:57动态规划解题步骤 1.定义子问题: 什么可以算得上有子问题,可以用动态规划解决的问题呢?例如在打家劫舍的算法题中,问题可以被拆分为各个子问题,子问题是打劫前k家能得到的最大金额。假设一共有 n 个房子的话,就...动态规划解题步骤
1.定义子问题:
什么可以算得上有子问题,可以用动态规划解决的问题呢?例如在打家劫舍的算法题中,问题可以被拆分为各个子问题,子问题是打劫前k家能得到的最大金额。假设一共有 n 个房子的话,就一共有 n个子问题。动态规划实际上就是通过求这一堆子问题的解,来求出原问题的解。这要求子问题需要具备两个性质:(1)原问题要能由子问题表示。例如这道小偷问题中,k=n 时实际上就是原问题。否则,解了半天子问题还是解不出原问题,那子问题岂不是白解了。
(2)一个子问题的解要能通过其他子问题的解求出。例如这道小偷问题中,f(k)可以由 f(k-1)和 f(k-2) 求出。这个性质就是教科书中所说的“最优子结构”。如果定义不出这样的子问题,那么这道题实际上没法用动态规划解。
2.写子问题的递推关系:
子问题之间存在一种递推关系。第k个子问题的结果是由第k-1或者k-2个子问题的结果得出的。
3.确定DP数组的计算顺序:
DP 数组也可以叫”子问题数组”,因为 DP 数组中的每一个元素都对应一个子问题。dp[k] 对应子问题 f(k),即偷前 k 间房子的最大金额。
4.空间优化
案例:(leetcode198)
代码:class Solution { public int rob(int[] nums) { int len = nums.length; int[] max = new int[len]; if(len == 0){ return 0; } if(len ==1){ return nums[0]; } max[0] = nums[0]; for(int i=1;i<len;i++){ max[i] = Math.max(max[i-1],(nums[i]+((i-2<0) ? 0:max[i-2]))) ; } return max[len-1]; } }
-
17.动态规划例题及解题步骤---最少硬币组合问题(求最大最小值动态规划)
2020-11-05 20:40:38二、分析:动态规划解题步骤包含四个部分 (1)部分一:确定状态 (1.1)最后一步 (1.2)子问题 (1.3)递归解法 (2)部分二:转移方程 (3)部分三:初始条件和边界情况 (4)第四... -
动态规划(二)解题步骤
2021-02-19 21:19:11动态规划解题套路 文章目录动态规划解题套路与贪心区别动规套路动规debug 与贪心区别 借鉴【代码随想录】大佬的一句话,动态规划就是由前一个状态推导出来的;贪心是局部选取最优,与前一状态无关。 动规套路 确定... -
图解动态规划的解题四步骤
2020-04-02 20:36:44如果你对于动态规划还不是很了解,...动态规划的的四个解题步骤是: 定义子问题 写出子问题的递推关系 确定 DP 数组的计算顺序 空间优化(可选) 下面我们一步一步地进行讲解。 步骤一:定义子问题 稍微接触过一点... -
动态规划解题思路
2020-11-30 16:57:59动态规划 一直以来都没有好好的了解动态规划问题,因为现在很多的笔试题中都会涉及动态规划的问题,所以通过学习动态规划来记录一下学习的笔记。...动态规划的解题步骤 1. 确定状态: 最后一步 关键 -
动态规划类问题解题步骤 --附例题(小偷问题)
2020-09-06 14:48:00动态规划类问题解题步骤 --附例题(小偷问题)动态规划基本思想适用情况优点解题步骤实例分析问题解题步骤 动态规划 基本思想 动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分... -
以凑硬币问题分析动态规划最值类解题步骤
2020-07-14 10:43:49首先根据最小两个字和题意可以分析是用动态规划来进行解题。 确定状态 解题的前提就是确定题中的状态是什么,一般情况下,动态规划需要开一个数组,数据的每个元素f(i)或者f(i)(j)代表的就是状态。 确定状态需要通过... -
贪心算法、动态规划(解题步骤、区别联系)
2020-07-11 22:50:132.动态规划 1.动态规划算法一般都有下面两种实现方式,前者称为递归版本,后者称为迭代版本,且两个版本是可以相互转换的。 - 1.直接自顶向下实现递归式,并将中间结果保存,这叫备忘录法; - 2.按照递归式自底向上... -
16. 动态规划概念、特点及解题步骤
2020-11-05 18:57:53一、状态压缩动态规划概念 二、例题1 -
动态规划解题方法与常见例题
2020-08-11 20:49:14解题步骤: 判题题意是否为找出一个问题的最优解 将原问题分解为子问题 从下往上分析问题 ,找出这些问题之间的关联(状态转移方程),如何从一个或多个已知状态求出另一个未知状态的值。(递推型) 讨论底层的边界... -
以不同路径问题分析动态规划计数类解题步骤
2020-07-14 10:42:25根据动态规划解题要素,分析如下: 确定状态 最后一步 这里的最后一步是走到网格的右下角,那么定义走到最后一个位置的路径数是f(i)(j),走到这一步只有两种可能,从上边来,或者从左边来。 子问题 从上边来为f(i-1)... -
【算法学习笔记】动态规划:解题思考步骤分析
2020-01-11 11:38:32动态规划(英语:Dynamic programming,简称 DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子... -
动态规划(二):以计算路径总数为例,继续总结动态规划解题思路
2020-07-03 22:18:30在上篇文章:以最简单的斐波拉契数列为例子初步认识动态规划中末尾,有讲到动态规划的解题思路,但在解析斐波拉契数列时,也许是大家对它很熟悉,所以对于递归 + 记忆化这一步骤感受可能不是特别深。接下来,将严格... -
Java数据结构和算法——动态规划做题步骤详细总结
2020-07-11 18:19:48文章目录动态规划题目类型动态规划解题步骤动态规划实例讲解硬币问题机器人路径问题青蛙跳石头问题 动态规划题目类型 1、计数: 有多少种方式走到右下角 有多少种方法选出k个数使得和为Sum 2、求最大最小值: 从左上... -
动态规划1--基本步骤
2021-01-26 12:01:44文章目录动态规划解题步骤:1、确定状态2、转移方程3、初始条件和边界情况4、确定计算顺序1、最值型动态规划 min/maxexample: CoinChange问题分析:1、最后一步:2、转移方程3、边界情况4、计算顺序:代码实现2、...
-
江西财经大学《公司金融》期末考试试卷和知识要点总结.pdf
-
Docker从入门到精通
-
【硬核】一线Python程序员实战经验分享(1)
-
最新Java JDK 11免安装版(MacOS 64位)
-
2021-03-02
-
最新版O泡易支付系统平台 PHP源码 第三方第四方免签支付平台系统 全开源可二开.zip
-
2021-03-02
-
华为1+X——网络系统建设与运维(高级)
-
C++之STL
-
最新Java JDK 8安装版(MacOS 64位)
-
八皇后
-
azkaban.pdf
-
NFS 实现高可用(DRBD + heartbeat)
-
Galera 高可用 MySQL 集群(PXC v5.6 + Ngin
-
「河北省考」河北公务员考试报名照片要求及怎么上传
-
2021-03-02
-
江西财经大学《金融企业会计》期末复习题(含答案).pdf
-
江西财经大学《微积分I》01-11年历年期末考试试卷(后面卷基本含答案).pdf
-
江西财经大学《思修》期末考试试卷.pdf
-
2021-03-02