算法-动态规划
在线测试
动态规划
斐波那契数
斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给你 n ,请计算 F(n) 。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/fibonacci-number
示例:
输入:4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3
示例代码:
int fib(int n) {
int F[n+1];
F[0] = 0;
if (n <= 0)
return F[0];
F[1] = 1;
if (n == 1)
return F[1];
for (int i = 2; i < n+1; i++)
{
F[i] = F[i - 1] + F[i - 2];
}
return F[n];
}
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
int climbStairs(int n){
int S[n+1];
S[1] = 1;
if (n == 1)
return S[1];
S[2] = 2;
if (n == 2)
return S[2];
for (int i = 3; i <= n; i++)
{
S[i] = S[i - 1] + S[i - 2];
}
return S[n];
}
使用最小花费爬楼梯
数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。
每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯。
int min(int a, int b)
{
return a>b?b:a;
}
int minCostClimbingStairs(int* cost, int costSize){
int C[costSize + 1];
C[0] = cost[0];
if (costSize == 1)
return C[0];
C[1] = min(C[0] + cost[1], cost[1]);
if (costSize == 2)
return min(C[0], C[1]);
for (int i = 2; i < costSize; i++)
{
C[i] = min(C[i - 1], C[i - 2]) + cost[i];
}
return min(C[costSize - 1], C[costSize - 2]);
}
Archives
2019/03 (14) 2020/08 (1) 2021/01 (2) 2021/05 (2) 2021/12 (2) 2022/03 (2) 2022/04 (2) 2023/12 (2) 2024/01 (5) 2024/04 (1) 2024/05 (1)Tags
Recent Posts