欢迎来到 破晓的历程的 博客

⛺️不负时光，不负己✈️

---

1.三步问题

1.题目连接

• 三步问题

---

2.算法原理讲解&&代码实现

• 动态规划–线性dp

  • 线性表示：

    • dp[i]:到达第i级台阶一共有多少种选择。

  • 状态转移方程

    • dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

class Solution {
public:int waysToStep(int n) {if(n==1||n==2)return n;if(n==3) return 4;vector<int> dp(n);for(int i=4;i<=n;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];}return dp[n];}
};

---

2.最小花费爬楼梯

1.题目连接

• 最小花费爬楼梯

---

2.算法原理讲解&&代码实现

方法1

• 动态规划–线性dp

  • 线性表示：

    • dp[i]:到达第i级台阶需要花费多少钱。

  • 状态转移方程

    • dp[i]=min（dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]）

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();if(n==1||n==0) return 0;vector<int> dp(n+1);dp[0]=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];}
};

---

方法2

• 动态规划–线性dp

  • 线性表示：

    • dp[i]:从i级台阶出发，爬到顶需要花费多少钱。

  • 状态转移方程

    • dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i])

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();if(n==0||n==1) return 0;vector<int> dp(n);dp[n-1]=cost[n-1];dp[n-2]=cost[n-2];for(int i=n-3;i>=0;i--){dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i]);}return dp[0]>dp[1]?dp[1]:dp[0];}
};

---

3.解码方法

1.题目连接

• 解码方法

---

2.算法原理讲解&&代码实现

• 动态规划–线性dp

  • 线性表示：

    • dp[i]:到达第i个字符一共有多少种解码方式。

  • 状态转移方程

    • dp[i]=dp[i-1]+dp[i-2]

class Solution {
public:int numDecodings(string s) {int n=sizeof(s);vector<int> dp(n);dp[0]=s[0]=!'0';if(n==1) return dp[0];if(s[1]!='0'&&s[1]!='0') dp[1]+=1;int ret=(s[0]-'0')*10+(s[1]-'0');if(ret>=10&&ret<=26) dp[1]+=1;for(int i=2;i<n;i++){if(s[i]!='0') dp[i]+=dp[i-1];int re=(s[i-1]-'0')*10+(s[i]-'0');if(re>=10&&re<=26) dp[i]+=dp[i-2];}return dp[n-1];}
};

---