江苏省建设厅网站,国内做网站大公司,wordpress商城开源,社区推广普通话#x1f4d8;北尘_#xff1a;个人主页 #x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上#xff0c;不忘来时的初心 文章目录 一、第N个泰波那契数1、题目讲解2、思路讲解3、代码实现 二、三步问题1、题目讲解2、思路讲解… 北尘_个人主页 个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上不忘来时的初心 文章目录 一、第N个泰波那契数1、题目讲解2、思路讲解3、代码实现 二、三步问题1、题目讲解2、思路讲解3、代码实现 三、使用最小花费爬楼梯1、题目讲解2、思路讲解3、代码实现 四、解码方法1、题目讲解2、思路讲解3、代码实现 一、第N个泰波那契数
1、题目讲解 2、思路讲解
状态表⽰ 这道题可以「根据题⽬的要求」直接定义出状态表⽰ dp[i] 表⽰第 i 个泰波那契数的值。状态转移⽅程 题⽬已经⾮常贴⼼的告诉我们了 dp[i] dp[i - 1] dp[i - 2] dp[i - 3]初始化 从我们的递推公式可以看出 dp[i] 在 i 0 以及 i 1 的时候是没有办法进⾏推导的因 为 dp[-2] 或 dp[-1] 不是⼀个有效的数据。 因此我们需要在填表之前将 0, 1, 2 位置的值初始化。题⽬中已经告诉我们 dp[0] 0, dp[1] dp[2] 1 。填表顺序 毫⽆疑问是「从左往右」。返回值 应该返回 dp[n] 的值。
3、代码实现 普通版 class Solution {
public:int tribonacci(int n) {if(n0) return 0;if(n1 || n2) return 1;vectorint dp(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];}
};空间优化版 class Solution {
public:int tribonacci(int n) {if(n0) return 0;if(n1 || n2) return 1;int a0,b1,c1,d0;for(int i3;in;i){dabc;ab;bc;cd;}return d;}
};二、三步问题
1、题目讲解 2、思路讲解 状态表⽰ 这道题可以根据「经验 题⽬要求」直接定义出状态表⽰ dp[i] 表⽰到达 i 位置时⼀共有多少种⽅法。状态转移⽅程 以 i 位置状态的最近的⼀步来分情况讨论 如果 dp[i] 表⽰⼩孩上第 i 阶楼梯的所有⽅式那么它应该等于所有上⼀步的⽅式之和 i. 上⼀步上⼀级台阶 dp[i] dp[i - 1] ii. 上⼀步上两级台阶 dp[i] dp[i - 2] iii. 上⼀步上三级台阶 dp[i] dp[i - 3] 综上所述 dp[i] dp[i - 1] dp[i - 2] dp[i - 3] 。 需要注意的是这道题⽬说由于结果可能很⼤需要对结果取模。 在计算的时候三个值全部加起来再取模即 (dp[i - 1] dp[i - 2] dp[i - 3]) % MOD 是不可取的同学们可以试验⼀下 n 取题⽬范围内最⼤值时⽹站会报错 signed integer overflow 。 对于这类需要取模的问题我们每计算⼀次两个数相加/乘等都需要取⼀次模。否则万⼀ 发⽣了溢出我们的答案就错了。初始化 从我们的递推公式可以看出 dp[i] 在 i 0, i 1 以及 i 2 的时候是没有办法进⾏ 推导的因为 dp[-3] dp[-2] 或 dp[-1] 不是⼀个有效的数据。 因此我们需要在填表之前将 1, 2, 3 位置的值初始化。 根据题意 dp[1] 1, dp[2] 2, dp[3] 4 。填表顺序 毫⽆疑问是「从左往右」。返回值 应该返回 dp[n] 的值。
3、代码实现
class Solution {
public:int waysToStep(int n) {if(n1 || n2) return n;if(n3) return 4;const int MOD1e97;vectorint dp(n1);dp[1]1,dp[2]2,dp[3]4;for(int i4;in;i){dp[i] ((dp[i - 1] dp[i - 2]) % MOD dp[i - 3]) % MOD;}return dp[n];}
};三、使用最小花费爬楼梯
1、题目讲解 2、思路讲解
方法一
状态表⽰ 这道题可以根据「经验 题⽬要求」直接定义出状态表⽰ 第⼀种以 i 位置为结尾巴拉巴拉 dp[i] 表⽰到达 i 位置时的最⼩花费。注意到达 i 位置的时候 i 位置的钱不需要 算上状态转移⽅程 根据最近的⼀步分情况讨论 ▪ 先到达 i - 1 的位置然后⽀付 cost[i - 1] 接下来⾛⼀步⾛到 i 位置 dp[i - 1] csot[i - 1] ▪ 先到达 i - 2 的位置然后⽀付 cost[i - 2] 接下来⾛⼀步⾛到 i 位置 dp[i - 2] csot[i - 2] 。初始化 从我们的递推公式可以看出我们需要先初始化 i 0 以及 i 1 位置的值。容易得到 dp[0] dp[1] 0 因为不需要任何花费就可以直接站在第 0 层和第 1 层上。填表顺序 根据「状态转移⽅程」可得遍历的顺序是「从左往右」。返回值 根据「状态表⽰以及题⽬要求」需要返回 dp[n] 位置的值。
方法二
状态表⽰ 这道题可以根据「经验 题⽬要求」直接定义出状态表⽰ 第⼆种以 i 位置为起点巴拉巴拉。 dp[i] 表⽰从 i 位置出发到达楼顶此时的最⼩花费。状态转移⽅程 根据最近的⼀步分情况讨论 ▪ ⽀付 cost[i] 往后⾛⼀步接下来从 i 1 的位置出发到终点 dp[i 1] cost[i] ▪ ⽀付 cost[i] 往后⾛两步接下来从 i 2 的位置出发到终点 dp[i 2] cost[i] 我们要的是最⼩花费因此 dp[i] min(dp[i 1], dp[i 2]) cost[i] 。初始化 为了保证填表的时候不越界我们需要初始化最后两个位置的值结合状态表⽰易得 dp[n - 1] cost[n - 1], dp[n - 2] cost[n - 2]填表顺序 根据「状态转移⽅程」可得遍历的顺序是「从右往左」。返回值 根据「状态表⽰以及题⽬要求」需要返回 dp[n] 位置的值。
3、代码实现
方法一
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int ncost.size();vectorint dp(n1);dp[0]0,dp[1]0;for(int i2;in;i){dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[n]; }
};方法二
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int ncost.size();vectorint dp(n);dp[n-1]cost[n-1],dp[n-2]cost[n-2];for(int in-3;i0;i--){dp[i]cost[i]min(dp[i1],dp[i2]);}return min(dp[0],dp[1]);}
};四、解码方法
1、题目讲解 2、思路讲解 状态表⽰ 根据以往的经验对于⼤多数线性 dp 我们经验上都是「以某个位置结束或者开始」做⽂章这 ⾥我们继续尝试「⽤ i 位置为结尾」结合「题⽬要求」来定义状态表⽰。 dp[i] 表⽰字符串中 [0i] 区间上⼀共有多少种编码⽅法。 状态转移⽅程 定义好状态表⽰我们就可以分析 i 位置的 dp 值如何由「前⾯」或者「后⾯」的信息推导出 来。 关于 i 位置的编码状况我们可以分为下⾯两种情况 i. 让 i 位置上的数单独解码成⼀个字⺟ ii. 让 i 位置上的数与 i - 1 位置上的数结合解码成⼀个字⺟。 下⾯我们就上⾯的两种解码情况继续分析 让 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 。 让 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 。 综上所述 dp[i] 最终的结果应该是上⾯四种情况下解码成功的两种的累加和因为我们关⼼ 的是解码⽅法既然解码失败就不⽤加⼊到最终结果中去因此可以得到状态转移⽅程 dp[i] 默认初始化为 0 i. 当 s[i] 上的数在 [1, 9] 区间上时 dp[i] dp[i - 1] ii. 当 s[i - 1] 与 s[i] 上的数结合后在 [10, 26] 之间的时候 dp[i] dp[i - 2] 如果上述两个判断都不成⽴说明没有解码⽅法 dp[i] 就是默认值 0 。
3、代码实现
优化前
class Solution {
public:int numDecodings(string s) {int ns.size();vectorint dp(n);dp[0]s[0]!0;if(n1) return dp[0];if(s[1]!0 s[0]!0) dp[1];int t(s[0]-0)*10(s[1]-0);if(t10 t26) dp[1];for(int i2;in;i){if(s[i]!0) dp[i]dp[i-1];int t(s[i-1]-0)*10(s[i]-0);if(t10 t26) dp[i]dp[i-2];}return dp[n-1];}
};
优化后
class Solution {
public:int ns.size();vectorint dp(n1);dp[0]1;dp[1]s[1-1]!0;for(int i2;in;i){if(s[i-1]!0) dp[i]dp[i-1];int t(s[i-2]-0)*10(s[i-1]-0);if(t10 t26) dp[i]dp[i-2];}return dp[n];}
};
