c++算法第4天
本篇文章包含三道算法题，难度由浅入深，适合新手练习哟
第一题
题目链接
牛牛的快递_牛客题霸_牛客网
题目解析
<=1kg -------> 20元 大于1kg：超出部分每千克1元
加急 5元
代码原理
代码编写
#include <iostream>
#include<cmath>
using namespace std;
int main() {
double a = 0.0;
char b;
int dollor = 0;
cin >> a >> b;
if(a <= 1)
{
if(b != 'y')
{
dollor += 20;
}
else {
dollor += 25;
}
}
if(a > 1)
{
if(b != 'y')
dollor = dollor + 20 + ceil(a - 1);
else
dollor = dollor + 20 + ceil(a - 1) + 5;
}
cout << dollor;
return 0;
}
当然啦，这题使用c语言也是一样的思路
本题总结
通过本题，我们需要了解的头文件有<cmath>(c++版本)<math.h>(c语言版本)
其次了解ceil这个库函数，ceil这个库函数的作用是向上取整
第二题
题目链接
. - 力扣（LeetCode）
题目解析
题目要求：返回第n个泰波那契数
题目条件：1. T0 = 0, T1 = 1,T2 = 2
2. T(n+3) = T(n) + T(n + 1) +T(n + 2) 这里，我们把这个条件处理一下——>T(n) = T(n - 3) + T(n - 2) + T(n - 1)
代码原理
由于博主也是第一次接触这个动态规划，但博主会尽可能地给大家讲懂，当然有疑惑，依旧可以在评论区留言
代码编写
class Solution {
public:
int tribonacci(int n) {
//边界情况处理
if(n == 0)
return 0;
if(n == 1 || n == 2)
return 1;
//创建dp表
vector<int> dp(n + 1);
//初始化
dp[0] = 0, dp[1] = dp[2] = 1;
//填表顺序
for(int i = 3; i <= n; i++)
{
dp[i] = dp[i -3] + dp[i - 2] + dp[i - 1];
}
//返回值
return dp[n];
}
};
本题总结
关于动态规划分析的题分五步
1.状态表示
2.状态转移方程
3.初始化（根据题目要求初始化，目的是防止越界）
4. 填表顺序
5.返回值
代码编写五步走
1.创建dp表
2.初始化（根据题目要求初始化，目的是防止越界）
3. 填表顺序
4.返回值
5.分析代码是否需要处理细节问题（如边界处理）
第三题
题目链接
最小花费爬楼梯_牛客题霸_牛客网
题目解析
代码原理
代码编写
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int cost[N];
//创建dp表
int dp[N];
int main() {
cin >> n;
//初始化
for(int i = 0; i < n; i++)
{
cin >> cost[i];
}
//状态转移方程
for(int i = 2; i <= n; i++)
{
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
cout << dp[n];
return 0;
}
本篇文章的算法题就先到这里，喜欢我的小伙伴给我点个关注，我怕你下次就找不到我了！
都看到这里了，给个三连呗，谢谢啦！
