欢迎来到Cefler的博客😁
🕌博客主页：那个传说中的man的主页
🏠个人专栏：题目解析
🌎推荐文章：题目大解析（3）
前言
算法原理
1.状态表示
是什么？dp表(一维数组)里面的值所表示的含义
怎么来？
（1）：题目要求 （2）：经验+题目要求 (3) :分析问题的过程中，发现重复子问题
2.状态转移方程
dp[i] = ?
3.初始化
保证填表的时候不越界
4.填表顺序
为了填写当前状态的时候，所需要的状态已经计算过了
5.返回值
题目要求+状态表示
编写代码四步骤：创建dp表->初始化->填表->返回值
👉🏻第 N 个泰波那契数
原题链接：第 N 个泰波那契数
mycode:
class Solution {
public:
int tribonacci(int n) {
//处理dp表可能越界情况
if(n==0)return 0;
if(n==1||n==2) return 1;
//1.建表
vector<int> v(n+1);
//2.初始化
v[0] = 0,v[1] = v[2] = 1;
//3.填表
for(int i = 3;i<=n;i++)
v[i] = v[i-3]+v[i-2]+v[i-1];
//返回值
return v[n];
}
};
空间优化
class Solution {
public:
int tribonacci(int n) {
//处理dp表可能越界情况
if(n==0)return 0;
if(n==1||n==2) return 1;
int a = 0,b = 1,c = 1,d = 0;
//3.填表
for(int i = 3;i<=n;i++)
{
d = a+b+c;
a = b;b = c; c = d;
}
//返回值
return d;
}
};
👉🏻三步问题
原题链接：三步问题
mycode:
class Solution {
public:
int waysToStep(int n) {
vector<int> v(n);
//考虑dp表越界情况
if(n==1)return 1;
else if(n==2)return 2;
else if(n==4)return 4;
//表初始化
v[0] = 1,v[1] = 2,v[2] = 4;
//填表
const int mod = 1e9+7;//10的9次方+7
for(int i = 3;i<n;i++)
{
v[i] = ((v[i-3]+v[i-2])%mod+v[i-1])%mod;
}
//返回值
return v[n-1];
}
};
👉🏻使用最小花费爬楼梯
原题链接：使用最小花费爬楼梯
解法一
状态表示：dp[i]就是第i个台阶花费的最小费用
mycode:
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
//dp[i]就是第i个台阶花费的最小费用
int n = cost.size();
vector<int> dp(n+1);
//考虑dp表越界可能
if(n<2)return 0;
//初始化dp表
dp[0] = dp[1] = 0;
for(int i = 2;i<=n;i++)
{
dp[i] = min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
}
//返回值
return dp[n];
}
};
解法二
状态表示：dp[i]就是第i个台阶出发到顶部的最小花费
状态转移方程可以为：dp[i] = min（dp[i+1]+cost[i],dp[i+2]+cost[i]）
mycode:
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
//dp[i]就是第i个台阶出发到顶部的最小花费
int n = cost.size();
vector<int> dp(n+1);
//考虑dp表越界可能
if(n<2)return 0;
//初始化dp表
dp[n] = 0,dp[n-1] = cost[n-1];
for(int i = n-2;i>=0;i--)
{
dp[i] = min(dp[i+1]+cost[i],dp[i+2]+cost[i]);
}
return min(dp[0],dp[1]);
}
};
小技巧：dp[i]状态如果推不出状态方程，就要试试换一下dp[i]状态了，因为原先的dp[i]状态表示可能是错的。
👉🏻解码方法
原题链接：解码方法
mycode:
class Solution {
public:
int ctoi(char c)
{
return c - '0';
}
int numDecodings(string s) {
//dp[i]表示到第i个位置的解码总数
vector<int> dp(s.size());
if(s[0]=='0') return 0;
//考虑dp表越界可能
if (s.size() == 1) return 1;
//初始化dp表
if (s[0] == '0') return 0;
dp[0] = 1;
int singlenum = ctoi(s[1]), unionnum = ctoi(s[0]) * 10 + ctoi(s[1]);
if (singlenum >= 1 && singlenum <= 26)
dp[1]++;
if (s[0] != '0' && (unionnum >= 1 && unionnum <= 26))
dp[1]++;
//开始填表
int n = s.size();
for (int i = 2; i < n; i++)
{
//单独解析
singlenum = ctoi(s[i]);
if (singlenum == 0)
{
dp[i - 1] = 0;
}
//组合解析
unionnum = ctoi(s[i-1]) * 10 + ctoi(s[i]);
if (s[i - 1] == '0' || (unionnum < 1 || unionnum>26))
dp[i - 2] = 0;
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n - 1];
}
};
简化代码：
优化代码：
如上便是本期的所有内容了，如果喜欢并觉得有帮助的话，希望可以博个点赞+收藏+关注🌹🌹🌹❤️ 🧡 💛,学海无涯苦作舟,愿与君一起共勉成长
