算法修炼-动态规划之斐波那契数列模型
一、动态规划的算法原理
这是本人动态规划的第一篇文章，所以先阐述一下动态规划的算法原理以及做题步骤。动态规划本人的理解就是通过题目所给的条件正确地填满dp表（一段数组）。首先要先确定好dp表每个位置的值所代表的含义是什么，然后通过题目条件以及经验推出状态转移方程，第三个就是初始化，确定填表顺序以及保证填表不越界，最后输出题目所需的结果，大致就是这个思路。
二、斐波那契数列模型例题分析
1137. 第 N 个泰波那契数 - 力扣（LeetCode）
本题的思路较为简单，状态转移方程已经给出，直接上代码：
class Solution {
public:
int tribonacci(int n)
{
vector<int> v1(n+1);
//初始化
if(n == 1)
return 1;
else if(n == 2)
return 1;
else if(n == 0)
return 0;
v1[0] = 0;
v1[1] = 1;
v1[2] = 1;
for(int i = 3; i <= n; i++)
{
v1[i] = v1[i-1] + v1[i-2] + v1[i-3];
}
return v1[n];
}
};面试题 08.01. 三步问题 - 力扣（LeetCode）
解析：
假设小孩此时正处于某一台阶上，那他是如何到达这一台阶的呢？是不是他有可能是从该台阶的前一个台阶跳上来的，也可能是从该台阶的前两个台阶跳上来的，也可能是从该台阶的前三个台阶跳上来的，所以小孩到某一台阶就有三种可能情况，也即dp表中某个位置的值就是这个位置前三个位置的值相加，从而确定出了状态转移方程。
class Solution {
public:
int waysToStep(int n)
{
//创建dp表
vector<int> v1(n+1);
if(n ==1)
return 1;
if(n == 2)
return 2;
if(n == 3)
return 4;
//初始化
v1[1] = 1;v1[2] = 2; v1[3] = 4;
for(int i = 4; i <= n; i++)
{
//确定状态转移方程，这里需要注意，加数的和可能会越界，根据题目要求要对1000000007取模
v1[i] = ((v1[i-1] + v1[i-2]) % 1000000007 + v1[i-3])%1000000007;
}
return v1[n];
}
};
解析：
要确定每一级楼梯最低花费，通过比较前两级楼梯，确定应该加的值，从而确定状态转移方程。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost)
{
int length = cost.size();
//dp表
vector<int> MinCost(length);
//初始化
for(int i = 0; i<cost.size(); i++)
{
MinCost[i] = cost[i];
}
//状态转移方程
for(int i = 2; i<length; i++)
{
if(MinCost[i-1] < MinCost[i-2])
{
MinCost[i] += MinCost[i-1];
}
else
{
MinCost[i] += MinCost[i-2];
}
}
if(MinCost[cost.size() - 1] < MinCost[cost.size() - 2])
{
return MinCost[cost.size() - 1];
}
else
{
return MinCost[cost.size() - 2];
}
}
};
解析：
选定一个位置作为结尾，如果这个位置的值不为零，就看其能否与前一个位置的值组成合法编码，如果能，这个位置的值就是它的前一个位置加上它的前前一个位置的值，如果不能，这个位置的值就是它的前一个位置的值；如果这个位置的值为零，就看其能否与前一个位置的值组成合法编码，如果能，这个位置的值就是它的前前一个位置的值。
class Solution {
public:
int numDecodings(string s)
{
int len = s.length();
int arr[len];
const char* str;
str = s.c_str();
for(int i = 0; i<len; i++)
{
arr[i] = str[i] - 48;
}
//处理特殊情况
if(arr[0] == 0)
{
return 0;
}
else if(len == 1 && arr[0] != 0)
{
return 1;
}
for(int i = 1; i<len; i++)
{
//例：30
if(arr[i] == 0 && (arr[i-1] >2))
{
return 0;
}
//例：1001
else if(i+1 < len && arr[i] == 0 && arr[i+1] == 0)
{
return 0;
}
}
for(int i = 0; i<len; i++)
{
cout << arr[i] << " ";
}
//dp表
vector<int> vect(len+1);
//初始化
vect[0] = 1;vect[1] = 1;
//状态转移方程
for(int i = 2; i < vect.size(); i++)
{
if(arr[i-1] != 0)
{
if(arr[i-2] != 0 && ((arr[i-1] + arr[i-2]*10) <= 26))
{
vect[i] = vect[i-1] + vect[i-2];
}
else
{
vect[i] = vect[i-1];
}
}
else
{
vect[i] = vect[i-2];
}
}
return vect[len];
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-03-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录