进度跟踪网站开发,化工网站模板,wordpress投票代码,南阳关键词优化创作不易#xff0c;感谢三连支持 #xff01; 斐波那契数列用于一维探索的单峰函数之中#xff0c;用于求解最优值的方法。其主要优势为#xff0c;在第一次迭代的时候求解两个函数值#xff0c;之后每次迭代只需求解一次 。
一、第N个泰波那契数
. - 力扣#xff08;… 创作不易感谢三连支持 斐波那契数列用于一维探索的单峰函数之中用于求解最优值的方法。其主要优势为在第一次迭代的时候求解两个函数值之后每次迭代只需求解一次 。
一、第N个泰波那契数
. - 力扣LeetCode第N个泰波那契数 class Solution {
public:int tribonacci(int n) {//边界情况if(n0||n1) return n;if(n2) return 1;//建表vectorint dp(n1);dp[1]dp[2]1;//开始填表for(int i3;in;i) dp[i]dp[i-1]dp[i-2]dp[i-3];return dp[n];}
};
时间复杂度ON,空间复杂度为ON
是否还有可以优化的方法呢那就是该题可以使用滚动数组 class Solution {
public:int tribonacci(int n) {//边界情况if(n0||n1) return n;if(n2) return 1;//滚动数组int a0,b1,c1,d0;//开始滚动for(int i3;in;i) {dabc;ab;bc;cd;}return d;}
};
时间复杂度ON,空间复杂度为O1
二、三步问题
. - 力扣LeetCode三步问题
思路1dp[i]表示从起点到达i位置一共有几种方法 class Solution {
public:int waysToStep(int n) {const int MOD1e97;//边界情况if(n1||n2) return n;if(n3) return 4;//建立dp表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])%MODdp[i-3])%MOD;return dp[n];}
};
思路2dp[i]表示从i位置到达终点一共有几种方法 class Solution {
public:int waysToStep(int n) {const int MOD1e97;//边界情况if(n1||n2) return n;if(n3) return 4;//建立dp表vectorint dp(n);//初始化dp[n-1]1,dp[n-2]2,dp[n-3]4;//填表for(int in-4;i0;--i) dp[i]((dp[i1]dp[i2])%MODdp[i3])%MOD;return dp[0];}
};
三、使用最小的花费爬楼梯
. - 力扣LeetCode使用最小的花费爬楼梯
方法1dp[i]表示从起点到i台阶的最小花费 class Solution {
public:int minCostClimbingStairs(vectorint cost) {int ncost.size();vectorint dp(n1);//开始填表for(int i2;in;i) dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);return dp[n];}
};
思路2我们也可以以i为起点让dp[i]表示到楼顶的最小花费 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]);}
};
四、解码方法
. - 力扣LeetCode解码方法 class Solution {
public:int numDecodings(string s) {int ns.size();vectorint dp(n);if(s[0]!0) dp[0];//处理边界情况if(n1) return dp[0];if(s[1]!0s[0]!0) dp[1];int t(s[0]-0)*10(s[1]-0);if(10tt26) 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(10tt26) dp[i]dp[i-2];}return dp[n-1];}
}; 我们会发现dp[1]的初始化和填表里面的过程非常相似所以我们可以用一个动态规划的小技巧——虚拟节点专门用来处理边界问题 class Solution {
public:int numDecodings(string s) {int ns.size();vectorint dp(n1);dp[0]1;if(s[0]!0) dp[1];//开始填表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(10tt26) dp[i]dp[i-2];}return dp[n];}
}; 先暂时更新到这后面有新的题目会持续更新
