算法-动态规划

在线测试

动态规划

斐波那契数

斐波那契数，通常用 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]);
}
comments powered by Disqus