【每日刷题】Day112
【每日刷题】Day112
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 1137. 第 N 个泰波那契数 - 力扣（LeetCode）
2. 面试题 08.01. 三步问题 - 力扣（LeetCode）
3. LCR 088. 使用最小花费爬楼梯 - 力扣（LeetCode）
1. 1137. 第 N 个泰波那契数 - 力扣（LeetCode）
//思路：动态规划。
class Solution {
public:
int tribonacci(int n)
{
int a = 0,b = 1,c = 1,ans = 0;
if(n==0) return 0;
if(n>0&&n<=2) return 1;
for(int i = 3;i<=n;i++)
{
//不断更新Tn+3 以及 Tn Tn+1 Tn+2的值
ans = a+b+c;
a = b;
b = c;
c = ans;
}
return ans;
}
};
2. 面试题 08.01. 三步问题 - 力扣（LeetCode）
//思路：动态规划。
class Solution {
public:
int waysToStep(int n)
{
//结果需要模上1e9+7
int flag = 1e9+7;
//小孩一次能走1、2、3步，将前三种台阶的情况初始化
if(n==1||n==2) return n;
if(n==3) return 4;
vector<int> dp(n+1);
dp[1] = 1,dp[2] = 2,dp[3] = 4;
for(int i = 4;i<=n;i++) dp[i] = ((dp[i-1]+dp[i-2])%flag+dp[i-3])%flag;
return dp[n];
}
};
3. LCR 088. 使用最小花费爬楼梯 - 力扣（LeetCode）
//思路：动态规划。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost)
{
int size = cost.size()+1;
vector<int> dp(size);
dp[0] = dp[1] = 0;
for(int i = 2;i<size;i++) dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
return dp[size-1];
}
};