装修公司做网站的好处,用什么软件做网站最快,咸阳网站建设多少钱,保洁公司网站源码目录 斐波那契数列模型
1. 第N个泰波那契数 2.使用最小花费爬楼梯
3.解码方法 学过算法的应该知道#xff0c;动态规划一直都是一个非常难的模块#xff0c;无论是状态转移方程的定义还是dp表的填表#xff0c;都非常难找到思路。在这个算法的支线专题中我会结合很多力…目录 斐波那契数列模型
1. 第N个泰波那契数 2.使用最小花费爬楼梯
3.解码方法 学过算法的应该知道动态规划一直都是一个非常难的模块无论是状态转移方程的定义还是dp表的填表都非常难找到思路。在这个算法的支线专题中我会结合很多力扣题型由简单到复杂带大家深度剖析动态规划类的题型欢迎大家关注啊。 顺序 题目链接-》算法思路-》代码呈现 斐波那契数列模型
动态规划类题目解题步骤
依据题目进行状态表示(dp[i]的含义)写出状态转移方程(类似于dp[i]dp[i-1]dp[i-2])为防止填表时数组越界对dp表进行初始化dp[0]dp[1]1搞清楚填表顺序从前往后或者从后往前利用dp表返回问题答案 1. 第N个泰波那契数
题目链接
https://leetcode.cn/problems/n-th-tribonacci-number/description/ 算法思路 1. 状态表⽰ 这道题可以「根据题⽬的要求」直接定义出状态表⽰ dp[i] 表⽰第 i 个泰波那契数的值。 2. 状态转移⽅程 题⽬已经⾮常贴⼼的告诉我们了 dp[i] dp[i - 1] dp[i - 2] dp[i - 3] 3. 初始化 从我们的递推公式可以看出 dp[i] 在 i 0 以及 i 1 的时候是没有办法进⾏推导的因为 dp[-2] 或 dp[-1] 不是⼀个有效的数据。因此我们需要在填表之前将 0, 1, 2 位置的值初始化。题⽬中已经告诉我们 dp[0] 0,dp[1] dp[2] 1 。 4. 填表顺序 毫⽆疑问是「从左往右」。 5. 返回值 应该返回 dp[n] 的值。 代码呈现
class Solution {public int tribonacci(int n) {if(n0){return 0;}if(n1||n2){return 1;}int[] dpnew int[n1];dp[0]0;dp[1]1;dp[2]1;for(int i3;in;i){dp[i]dp[i-1]dp[i-2]dp[i-3];}return dp[n];}
} 2.使用最小花费爬楼梯
题目链接
https://leetcode.cn/problems/min-cost-climbing-stairs/description/ 算法思路 1. 状态表⽰ 这道题可以根据「经验 题⽬要求」直接定义出状态表⽰ dp[i] 表⽰到达 i 位置时的最⼩花费。注意到达 i 位置的时候 i 位置的钱不需要算上 2. 状态转移⽅程 根据最近的⼀步分情况讨论 先到达 i - 1 的位置然后⽀付 cost[i - 1] 接下来⾛⼀步⾛到 i 位置 dp[i - 1] csot[i - 1] 先到达 i - 2 的位置然后⽀付 cost[i - 2] 接下来⾛⼀步⾛到 i 位置 dp[i - 2] csot[i - 2] 。 3. 初始化 从我们的递推公式可以看出我们需要先初始化 i 0 以及 i 1 位置的值。容易得到dp[0] dp[1] 0 因为不需要任何花费就可以直接站在第 0 层和第 1 层上。 4. 填表顺序 根据「状态转移⽅程」可得遍历的顺序是「从左往右」。 5. 返回值 根据「状态表⽰以及题⽬要求」需要返回 dp[n] 位置的值。 代码呈现
class Solution {public int minCostClimbingStairs(int[] cost) {int sizecost.length;if(size2) return Math.min(cost[0],cost[1]);int[] dpnew int[size1];dp[0]0;dp[1]0;dp[2]Math.min(cost[0],cost[1]);for(int i3;isize;i){dp[i]Math.min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[size];}
}
3.解码方法
题目链接
https://leetcode.cn/problems/decode-ways/ 算法思路 类似于斐波那契数列 1. 状态表⽰ 根据以往的经验对于⼤多数线性 dp 我们经验上都是「以某个位置结束或者开始」做⽂章这 ⾥我们继续尝试「⽤ i 位置为结尾」结合「题⽬要求」来定义状态表⽰。 dp[i] 表⽰字符串中 [0 i] 区间上⼀共有多少种编码⽅法。 2. 状态转移⽅程 定义好状态表⽰我们就可以分析 i 位置的 dp 值如何由「前⾯」或者「后⾯」的信息推导出 来。 关于 i 位置的编码状况我们可以分为下⾯两种情况 i. 让 i 位置上的数单独解码成⼀个字⺟ ii. 让 i 位置上的数与 i - 1 位置上的数结合解码成⼀个字⺟。 下⾯我们就上⾯的两种解码情况继续分析 让 i 位置上的数与 i - 1 位置上的数结合在⼀起解码成⼀个字⺟也存在「解码成功」和「解码失败」两种情况 i. 解码成功当结合的数在 [10, 26] 之间的时候说明 [i - 1, i] 两个位置是可以解码成功的那么此时 [0, i] 区间上的解码⽅法应该等于 [0, i - 2 ] 区间上的解码⽅法原因同上。此时 dp[i] dp[i - 2] ii. 解码失败当结合的数在 [0, 9] 和 [27 , 99] 之间的时候说明两个位置结合后解码失败这⾥⼀定要注意 00 01 02 03 04 ...... 这⼏种情况那么此时 [0, i] 区间上的解码⽅法就不存在了原因依旧同上。此时 dp[i] 0 。 让 i 位置上的数单独解码成⼀个字⺟就存在「解码成功」和「解码失败」两种情况
i. 解码成功当 i 位置上的数在 [1, 9] 之间的时候说明 i 位置上的数是可以单独解 码的那么此时 [0, i] 区间上的解码⽅法应该等于 [0, i - 1] 区间上的解码⽅ 法。因为 [0, i - 1] 区间上的所有解码结果后⾯填上⼀个 i 位置解码后的字⺟就 可以了。此时 dp[i] dp[i - 1]
ii. 解码失败当 i 位置上的数是 0 的时候说明 i 位置上的数是不能单独解码的那么此时 [0, i] 区间上不存在解码⽅法。因为 i 位置如果单独参与解码但是解码失败了那么前⾯做的努⼒就全部⽩费了。此时 dp[i] 0 。 3. 初始化 ⽅法⼀直接初始化 由于可能要⽤到 i - 1 以及 i - 2 位置上的 dp 值因此要先初始化「前两个位置」。 初始化 dp[0] i. 当 s[0] 0 时没有编码⽅法结果 dp[0] 0 ii. 当 s[0] ! 0 时能编码成功 dp[0] 1 初始化 dp[1] i. 当 s[1] 在 [1 9] 之间时能单独编码此时 dp[1] dp[0] 原因同上 dp[1] 默认为 0 ii. 当 s[0] 与 s[1] 结合后的数在 [10, 26] 之间时说明在前两个字符中⼜有⼀种 编码⽅式此时 dp[1] 1 ⽅法⼆添加辅助位置初始化 可以在最前⾯加上⼀个辅助结点帮助我们初始化。使⽤这种技巧要注意两个点 i. 辅助结点⾥⾯的值要保证后续填表是正确的 ii. 下标的映射关系 4. 填表顺序 毫⽆疑问是「从左往右」 5. 返回值 应该返回 dp[n - 1] 的值表⽰在 [0, n - 1] 区间上的编码⽅法。 代码呈现
class Solution {public int numDecodings(String s) {char[] arrs.toCharArray();int narr.length;int[] dpnew int[n1];dp[0]1;if(arr[0]0) dp[1]0;else dp[1]1;if(n1){return dp[1];}for(int i2;in1;i){if(arr[i-1]!0){dp[i]dp[i-1];}if(((arr[i-2]-0)*10(arr[i-1]-0))26((arr[i-2]-0)*10(arr[i-1]-0))10){dp[i]dp[i-2];}}return dp[n];}
}
