PS:以下代码由C++实现
1.第N个泰波那契数 力扣
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
示例 1：
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4示例 2：
输入：n = 25
输出：1389537来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/n-th-tribonacci-number
class Solution {
public:
int tribonacci(int n)
{
int dp[4]={0};//创建dp表
dp[0]=0;//初始化
dp[1]=1;
dp[2]=1;
for(int i=3;i<=n;i++)
{
dp[i%4]=dp[(i-1)%4]+dp[(i-2)%4]+dp[(i-3)%4];//状态标识+填表顺序
}
return dp[n%4];
}
};2.三步问题· 力扣
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:
输入：n = 3
输出：4
说明: 有四种走法示例2:
输入：n = 5
输出：13来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/three-steps-problem-lcci
//这题和上一道题差不多
class Solution {
public:
int waysToStep(int n)
{
size_t dp[4]={0};
dp[0]=1;
dp[1]=1;
dp[2]=2;
dp[3]=4;
for(int i=3;i<=n;i++)
{
dp[i%4]=(dp[(i-1)%4]+dp[(i-2)%4]+dp[(i-3)%4])%1000000007;
}
return dp[n%4];
}
};3.使用最小花费爬楼梯 力扣
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/min-cost-climbing-stairs
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost)
{
int n=cost.size();
vector<int> str(n+1,0);//创建dp表
for(int i=2;i<=n;i++)
{
str[i]=min(cost[i-1]+str[i-1],cost[i-2]+str[i-2]);//状态表示
}
return str[n];//返回值
}
};4。 解码方法 力扣
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。示例 3：
输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。文章来源：https://www.toymoban.com/news/detail-603755.html来源：力扣（LeetCode）文章来源地址https://www.toymoban.com/news/detail-603755.html
class Solution {
public:
int numDecodings(string s)
{
int n=s.size();
vector<int> dp(n+1);
dp[0]=1;//处理后边的情况
dp[1]=s[0]!='0';
for(int i=2;i<=n;i++)
{
if(s[i-1]!='0') dp[i]+=dp[i-1];//处理单独编码的情况
int num=(s[i-2]-'0')*10+(s[i-1]-'0');
if(num>=10&&num<=26) dp[i]+=dp[i-2];
}
return dp[n];
}
};到了这里，关于C++ 一维动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
