网站做接口到app价格,华龙建设部网站查不到,购物网站建设的目标,中国电力建设集团有限公司Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏#xff1a; 算法Journey #x1f3e0; 第N个泰波那契数模型
#x1f4cc; 题目解析 第N个泰波那契数 题目要求的是泰波那契数#xff0c;并非斐波那契数。
s Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏 算法Journey 第N个泰波那契数模型 题目解析 第N个泰波那契数 题目要求的是泰波那契数并非斐波那契数。 算法原理 递归
函数设置我们可以设置一个Taibo()函数它能帮我们求出第n个泰波那契数。
函数返回值题目保证answer 2^31 - 1设置为int即可。
函数实现根据定义求泰波那契数,我们需要前三个的泰波那契数相加,也就是Taibo(n-3) Taibo(n-2) Taibo(n-1)。
函数边界条件对于n 0,1,2是边界情况我们可以提前处理。
参考代码
class Solution {
public:long Taibo(int n){if(n 0)return 0;if(n 1 || n 2)return 1;return Taibo(n-1) Taibo(n-2) Taibo(n-3);}int tribonacci(int n){return Taibo(n);}
}; 记忆化搜索
对于解法一存在下面的问题 我们发现在递归过程有的节点的值(比如上图的Taibo(3))在第3层就已经求得了但是其他节点递归深入时又重新计算了导致了不必要的时间和栈空间的开销(时间复杂度O(3^n),空间复杂度O(N))。本题虽然n最大为37但其实栈空间和时间开销已经很大了肯定会超时我们可以采取记忆化搜索的方法
1. 添加一个备忘录。
2. 每次递归返回时将结果放到备忘录里面。
3. 在每次进入递归时往备忘录里查询是否已经记录。
参考代码
class Solution {
public:vectorint memory;long Taibo(int n){if (memory[n] ! -1) //查看备忘录return memory[n];long ret Taibo(n - 1) Taibo(n - 2) Taibo(n - 3);;memory[n] ret; //存进备忘录return ret;}int tribonacci(int n){memory.resize(38, -1); //创建一个备忘录memory[0] 0;memory[1] memory[2] 1;return Taibo(n);}
};
此时比之前大大避免了不必要的时间开销时间复杂度是(n)。 动态规划
我们动态规划分为以下几步
1. 状态表示
所谓状态表示其实是dp表里每个值代表的含义。 Q状态从何而来 题目要求(比如本题已经告诉我们要求的是第n个泰波那契数)。经验 题目要求(后面我们再提)。分析问题的过程发现重复的子问题。
因此本题dp[i]的含义是第i个泰波那契数。
2. 状态转移方程 状态转移方程回答的是dp[i]怎么得到的问题一般我们从最近一步得到。 比如本题中由定义知在 n 0 的条件下 Tn3 Tn Tn1 Tn2不就是dp[i] dp[i-1] dp[i-2] dp[i-3]吗
3. 初始化 初始化保证我们填表的时候不发生越界 当遇到n2时此时n-3-1很明显会会发生越界因此对于边界情况我们可以提前确定好边界位置在dp表中的值即dp[0] 0, dp[1] dp[2] 1。
4. 填表顺序 动态规划需要状态的推导只有确定好填表顺序才能确保在填写当前状态时所需要的状态已经计算过了。 本题很明显是从左往右填表。
5. 返回值 我们需要根据题目要求状态表示来确定返回值。 注dp[i]不一定就是我们所需的返回值我们还需结合题目要求本题dp[n]就是我们需要的返回值。
参考代码
class Solution
{
public:int tribonacci(int n){//1.状态表示dp[i]表示第N个泰波那切数vectorint dp(38,-1);//2.初始化dp[0] 0;dp[1] dp[2] 1;//3.填表for(int i 3 ; i n ; i ){dp[i] dp[i-1] dp[i-2] dp[i-3];//4.状态转移方程} return dp[n];//5.返回值}
}; 时间复杂度ON 空间复杂度O1 滚动数组
我们用vector容器来模拟dp表但其实可以进一步优化当求dp[i]只有前面的若干个状态最前面的几个状态不需要浪费空间此时可以使用滚动数组优化 我们可以利用四个变量来储存最近一次求泰波那契数的四个状态不断进行滚动最终求得目标结果 注对于赋值顺序不能从右往左赋即c d,b c, a b因为d给c之后c被d覆盖了但是b想要的是c的而c原本的值被覆盖了 参考代码
class Solution
{
public:int tribonacci(int n){//1.状态表示dp[i]表示第N个泰波那切数if (n 0) return 0;if (n 1 || n 2) return 1;int a 0;int b 1;int c 1;int d 0;//3.填表for (int i 3; i n; i){d a b c;;//状态转移方程a b;b c;c d;}return d;}
}; 三步问题 题目解析 三步问题 算法原理
1. 状态表示(经验 题目要求)
状态表示dp[i]表示到达i位置时一共有多少种方法。
2. 状态转移方程
我们从i位置的状态最近的一步来划分问题由于小孩一次可以上1阶2阶3阶
从i-1位置上来此时dp[i] dp[i-1]。从i-2位置上来此时dp[i] dp[i-2]。从i-3位置上来此时dp[i] dp[i-3]。
因此状态转移方程dp[i] dp[i-1] dp[i-2] dp[i-3]。
3. 初始化 对于第123级的台阶取它们的最近状态可能会造成数组越界(比如i为2时i-3得-1会越界)因此我们可以提前设置好它们的状态dp[1] 1 , dp[2] 2dp[3] 4。
4. 填表顺序
由状态转移方程知我们i位置的状态依赖于前几个位置的状态因此我们填表顺序是从左往右填。
5.返回值
我们要求的是上到第n阶楼梯的总方法直接返回dp[n]即可注意要对结果模1000000007。
参考代码
class Solution
{
public:int waysToStep(int n){if(n 1 || n 2) return n;if(n 3) return 4;long a 1; //dp[1]long b 2; //dp[2] long c 4; //dp[3]long d 0; for(int i 4 ; i n ; i ) //空间优化{d (a b c)%1000000007; //状态转移方程a b;b c;c d;} return d;}
}; 最小花费爬楼梯 题目解析 最小花费爬楼梯 假设n为数组元素个数则本题中楼梯顶部指的是dp[n]并非dp[n-1]。 算法原理 解法一 (以i位置为结尾)
1. 状态表示
dp[i]表示:到达 i 位置时,所需支付的最少费用。
2. 状态转移方程
用i位置的最近一步(之前或之后的状态)推导出dp[i]的值。
当到达i-1位置时支付cost[i-1],走一步到达i位置 - dp[i-1] cost[i-1]。当到达i-2位置时支付cost[i-2],走两步到达i位置 - dp[i-2] cost[i-2]。我们要么选择从i-1位置到i要么选择从i-2位置到i我们要的是最小花费则选最小的即可。
因此状态转移方程dp[i] min(dp[i-1]cost[i-1] , dp[i-2] cost[i-2])。
3.初始化
我们需要保证填表的时候不越界本题可以选择从下标为0或下标为1的位置开始爬楼梯因此这两个位置最初的花费是0即dp[0] dp[1] 0。
4. 填表顺序
根据我们的状态转移方程我们需i位置之前的状态因此填表顺序是从左往右填。
5. 返回值
返回达到楼梯顶部的最低花费,返回dp[n]即可。
参考代码
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();if(n 1 || n 0) return 0;vectorint dp(n1);dp[0] dp[1] 0 ; //初始化for(int i 2 ; i n ; i ) {dp[i] min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);} //状态转移方程return dp[n]; //返回值}
}; 解法二 (以i位置为起点)
1. 状态表示
dp[i]表示:从i位置出发,所需支付的最少费用。
2. 状态转移方程
用i位置的最近一步(之前或之后的状态)推导出dp[i]的值。
支付cost[i], 往后走一步,从i1的位置出发到终点 - dp[i1] cost[i]支付cost[i], 往后走两步,从i2的位置出发到终点 - dp[i2] cost[i]我们从i位置要么选择走一步到终点要么选择走两步到终点,我们要的是最小花费则选最小的即可。
因此状态转移方程dp[i] min(dp[i1] cost[i] , dp[i2] cost[i])。
3.初始化
对于n-1位置和n-2位置作为出发点,此时他们走一步或两步就到顶部了,因此i1和i2会使他们越界,我们只需支付他们对应的cost即可,即dp[n-1] cost[n-1] dp[n-2] cost[n-2]。
4. 填表顺序
根据我们的状态转移方程我们需i位置之后的状态因此填表顺序是从右往左填。
5. 返回值
我们是从0或1位置为起点出发的我们返回两者最小即可即min(dp[0],dp[1])。
参考代码
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorint dp(n);dp[n-2] cost[n-2] ;dp[n-1] cost[n-1];for(int i n-3 ; i 0 ; i--){dp[i] min(dp[i1]cost[i],dp[i2]cost[i]);} return min(dp[1],dp[0]);}
}; 解码方法 题目解析 91. 解码方法 - 力扣LeetCode 本题可能存在无法解码的字符串。字符串中可能包含前导0。 算法原理
1.状态表示
根据经验题目要求我们可以设置dp[i]的状态字符串以i位置结尾时解码方法的总数。
2. 状态转移方程
我们还是按照最近一步来划分问题对于i位置的解码我们以下两种情况
(1) s[i] 单独解码
解码成功(1 s[i] 9,‘0’无法参与解码),此时解码总方法等于前一个位置的解码方法总数即dp[i-1]。 解码失败此时为0。
(2) s[i] 与 s[i-1]解码
解码成功(0 b*10a 26)时解码总方法等于第i-2个位结尾字符串的解码方法总数即dp[i-2]。 解码失败此时为0。
因此状态转移方程为dp[i] dp[i-1] dp[i-2]
3. 初始化
(1) i 0时位于字符串的第一个字符我们只需判断它单独解码情况是否成立取值可能为01。
(2) i 1时位于字符串的第二个字符首先要单独解码就得先判断第一个字符能否单独解码否则没意义能单独解码则dp[1]再判断与s[0]是否能解码能则dp[1]。其可能取值为012。
4. 状态转移方程
根据状态转移方程我们需要之前位置的状态因此填表顺序是从左往右。
5. 返回值
由题意得最终需要的是以size-1为位置结尾的字符串的所有解码方法因此返回dp[size-1]。
参考代码
class Solution {
public:int numDecodings(string s){int n s.size();vectorint dp(n);dp[0] s[0] ! 0;//初始化处理边界if(n 1) return dp[0];if(s[0] ! 0 s[1] ! 0) dp[1] 1;//s[1]单独解码int t (s[0]-0)*10 s[1] - 0; if(t 10 t 26) dp[1] 1 ;//s[1]与前一个位置解码for(int i 2 ; i n ; i ){//一个数编码if(s[i] ! 0) dp[i] dp[i-1];//两个数编码int t (s[i-1]-0)*10 s[i] - 0; if(t 10 t 26) dp[i] 1;}return dp[n-1];}
}; 优化(虚拟节点) Q我们发现这两段代码相似度较高处理逻辑是一样的能不能把边界情况放进循环里处理呢 这里我们介绍一下虚拟节点 我们可以在原dp表基础上扩充一个位置,保证最后一个位置下标为n,这样在处理字符串中原来下标为0位置的字符时,它在新dp表的下标变为1,这样i-1就不会越界!但是同时要注意两个问题:
1. 虚拟节点里面的值,要保证后面的填表时正确的。(比如对于新dp表的0下标位置我们要保证对于如果字符串第二个位置的字符能跟第一个字符解码此时需要新dp表i-2位置的值也就是dp[0]此时我们需要设置它为1表示存在第二个字符和第二个字符共同解码这一种解码方法)
2. 下标的映射关系我们新dp表下标在原来基础上1但是s[i]的size并没有变化
class Solution
{
public:int numDecodings(string s)
{
//优化int ns.size();vectorintdp(n 1);dp[0]1;//保证后面的填表是正确的dp[1] s[1 - 1] ! 0;
注意映射关系s[1-1]下标映射关系for(inti2;in;i){if(s[i-1]!0)dp[i]dp[i-1];//处理单独编码的情况int (s[i-2]-0)*10s[i-1]-0;//第二种情况所对应的数if(t10 t26)dp[i]dp[i] dp[i - 2];}return dp[n];
} 完。
