【动态规划】斐波那契数列模型 |
您所在的位置：网站首页 › python123斐波那契数列 › 【动态规划】斐波那契数列模型 |
【动态规划】斐波那契数列模型
|
冻龟算法系列之斐波那契数列模型
动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 至于这个模型是什么意思，我觉得你往下看下去，自主感受那些相似之处，才不会懵逼~ 而本文为动态规划系列的第一篇，所以在动态规划做题步骤上会比较分明，接下来的几道例题，让我们边实战边学吧！ 文章解题的大的流程为： 题目解析算法原理（可能会有其他解法，在这个系列只讲解动态规划的思想）编写代码空间优化 动态规划一般很难，做出来已经不错了，所以主要重心放在解题上本文第一道题，把所有流程都会过一遍，所以会讲，而在讲背包问题之前，都不会出现这个步骤因为动态规划一般会比较浪费空间，所以才有这个空间优化的必要 1. 第N个泰波那契数传送门：力扣1137 题目：
所以有以下示例：
同理：
算法原理分析的过程分五步： 画出dp表并确定dp表**状态表示**根据状态表示确定**状态转移方程****初始化**dp表确定**填表顺序**确定**返回值**由于是第一道题，所以下面是细致讲解！ 但是因为这道题比较简单，一些方面没有涉及到，但是对于初学者，这样才最友好，因为本题重点就是熟悉做题流程！在后续的学习中，反复积累经验，了解方方面面，再依此基础上去刷题，才能学好动态规划！ 1.2.1 状态表示什么是状态表示： 这就涉及动态规划的核心：dp表 这个dp表的建立是不固定的，可能是一维数组，二维数组等等…而dp表中的元素与其对应下标有什么关系，即这个元素的**含义**，或者说是这个元素所处的“状态”（抽象笼统的说法） 而其中，我们要的答案，就是dp表其中的一个元素例子： 开心or不开心，是状态1下标元素的含义就是滑稽老铁开心
而设立的状态表示不一样，也意味着思路不一样，即不同的解法~ 想到一个，然后就去试试能不能解…做多点题，这一步准确率会高点~怎么来？ 经验 + 题目要求分析问题的过程中，发现重复的子问题，抽象成状态表示（暂时不讲）而这道题，我们只需建立一个一维dp表（大小为n + 1）： 题目要求：返回第n个泰波那契数的值经验：dp[n]应该就是答案
即dp[i]表示：第 i 个泰波那契数的值 1.2.2 状态转移方程什么是**状态转移方程**： 就是，dp[i] = … ;而这个方程可能有条件，分支，循环等复杂的逻辑…而dp[i]是由dp表其他下标对应的值来推导出来的 比如，dp[i]之前或者之后的值可以推出dp[i]例子： 开心是会传染的：
而本题的动态转移方程就是： dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; 难的方程怎么推导？ 遇到再说现在纸上谈兵没有意义对应动态规划的题目而言，前两步是最最重要的，也就是百分之99已完成~ 接下来就是一些细节的处理 1.2.3 初始化 很明显，通过已知推未知的过程中，会遇到一些数组越界等问题…，而初始化就是为了解决这些问题本题为： i - 1，i - 2，i - 3要有意义，则i要大于等于3所以在初始化的时候，手动给dp[0]、dp[1]、dp[2]赋值（赋值之前要确保不越界，越界就直接返回即可） 1.2.4 填表顺序我们通过已知推未知，这里的已知可能是i之前或者i之后，这就分为了简单的两个大方向（一维dp表） 本题为：顺序1 要保证填这个下标的时候，需要用到的其他下标，是已经在此之前填了的！ 即，计算过了的 1.2.5 返回值根据题目要求 + 状态表示得出返回值 本题为：dp[n] 注意下标确定是哪个可以说返回值和状态表示是同时确定的 1.3 编写代码编写代码分为固定的四步： 创建dp表初始化算法主体（填表）返回值 class Solution { public int tribonacci(int n) { //1. 创建dp表 int[] dp = new int[n + 1]; //2. 初始化 if(n == 0) { return 0; } if(n == 1 || n == 2) { return 1; } dp[0] = 0; dp[1] = 1; dp[2] = 1; //3. 填表 for(int i = 3; i public int tribonacci(int n) { //1. 空间优化 int[] src = new int[3]; src[0] = 0; src[1] = 1; src[2] = 1; //2. 初始化 if(n == 0) { return 0; } if(n == 1 || n == 2) { return 1; } int ret = 0; //3. 填表 for(int i = 3; i public int waysToStep(int n) { //1. 创建表 int[] dp = new int[n + 1]; int MOD = (int)1e9 + 7; //取模数 //2. 初始化，处理边界问题 if(n == 1) { return 1; } if(n == 2) { return 2; } if(n == 3) { return 4; } dp[1] = 1; dp[2] = 2; dp[3] = 4; //3. 填表 for(int i = 4; i public int minCostClimbingStairs(int[] cost) { int n = cost.length; //1. 创建dp表 int[] dp = new int[n + 1]; //2. 初始化，处理边界 if(n == 0 || n == 1) { return 0; } dp[0] = 0; dp[1] = 0; //3. 填表 for(int i = 2; i public int minCostClimbingStairs(int[] cost) { int n = cost.length; //1. 创建dp表 int[] dp = new int[n + 1]; //2. 初始化，处理边界 if(n == 0 || n == 1) { return 0; } dp[n] = 0; dp[n - 1] = cost[n - 1]; //3. 填表 for(int i = n - 2; i >= 0; i--) { dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i]; } //4. 返回值 return Math.min(dp[0], dp[1]); } }
所以状态表示的不同，算法思路就有所不同，至于怎么选中呢？ 做题多，经验多想到一个，就想尽方法去用这一个去解决问题，解决不了再换（敢于尝试） 4. 解码方法传送门：力扣91 题目：
对于示例，目前看不出什么~ 显然，也是一维的dp表（大小为n） 题目要求：输入字符串，返回整个字符串能反解出来的解的个数 经验：以某个节点为终点 那么这个终点只能是字符串的某个字符了~而答案应该为dp[n - 1]（dp表的其中一值）
那么我们趋向于让答案合理的为dp[n - 1]: 得到状态表示：dp[i]代表字符串[0, i]的子串最多能反解出来的解的个数 4.2.2 状态转移方程同样的，我们把dp[i]之前的值视为“已知”，把它们当做条件，去推导dp[i] 那么，要扩展到[0, i]的字符串，则扩展成[0, i]字符串之前，应该为[0, i - 1]的子串或者[0, i - 2]的子串: 如果是[0, i - 1]的子串，则字符串的第i个字符应该单独转化为字母才行，不然前功尽弃！ 反解成功：dp[i - 1]反解失败：0 如果是[0, i - 2]的子串，则字符串的第i - 1和第i个字符应该成双转化为字母(06之类的不行！)才行，否则前功尽弃！ 反解成功：dp[i - 2]反解失败：0为什么不可以各自可转化为字母也行? 第i - 1个字符可以单独反解和第i个字符也可以单独反解，此解法在情况1出现过得出状态转移方程： dp[i] = (dp[i - 1]) + (dp[i - 2]); 前提是对应项满足条件 4.2.3 初始化对于0和1下标要特殊处理： 0的话 如果可以单独成字母 => 1不可以 => 01的话 成双结合成字母 => +1各自单独成字母 => +1都不可以 => 0 4.2.4 填写顺序由于是以某个节点为终点，所以填写顺序为从左到右~ 4.2.5 返回值返回dp[n - 1]，代表整个字符串能反解的解的个数 4.3 编写代码 class Solution { public int numDecodings(String s) { int n = s.length(); char[] string = s.toCharArray(); //创建dp表 int[] dp = new int[n]; //初始化并处理边界问题 if(string[0] != '0') { dp[0] = 1; } if(n == 1) { return dp[0]; } if(string[0] !='0' && string[1] != '0') { dp[1]++; } int number = (string[0] - '0') * 10 + string[1] - '0'; if(number >= 10 && number if(string[i] != '0') { dp[i] += dp[i - 1]; } number = (string[i - 1] - '0') * 10 + string[i] - '0'; if(number >= 10 && number public int numDecodings(String s) { int n = s.length(); char[] string = s.toCharArray(); int[] dp = new int[n + 1]; dp[0] = 1; if(string[0] != '0') { dp[1] += 1; } if(n == 1) { return dp[1]; } for(int i = 2; i dp[i] += dp[i - 1]; } int number = (string[i - 2] - '0') * 10 + string[i - 1] - '0'; if(number >= 10 && number |
【本文地址】
今日新闻 |
推荐新闻 |