剑指offer-9.斐波那契数列

0 题目

现在要求输入一个整数n，输出斐波那契数列的第n项。

1 分析

传统递归实现，需要求多个重复子问题。

使用动态规划，memo记录，但是，只是用了两个。

因此改进冬天规划

2 实现

普通的动态规划

int Fibonacci(int n)
{
    vector<int> memo = {0, 1};

    for (int i = 2; i <= n; ++i)
    {
        memo.push_back(memo[i - 2] + memo[i - 1]);
    }
    return memo[n];
}

　　

使用三个int不停的交换

int Fibonacci(int n)
{
    if (n == 0)
    {
        return 0;
    }
    if (n == 1)
    {
        return 1;
    }

    int a = 0, b = 1;
    int m = 0; //交换用的。
    int i;
    // 0，1的时候已经输出了，因此这里从2开始
    for (i = 2; i <= n; i++)
    {
        m = a + b;
        a = b; //保持a永远是第一个
        b = m; //b永远是第二个
    }
    return m;
}

　　

3 拓展

3.1 题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析，f(n)=f(n-1)+f(n-2)

f(i)跳到第i层可能的方法。

f(0)=0

f(1)=1

f(2)=2

f(3)=f(2)+f(1) 也就是说，从f(2)调到f(3),和从f(1)调到f(3)

因此，与斐波那契数列不同之处在于，这个题目是从第三个开始的有地推公式的。

int jumpFloor(int number)
{
    if (number == 1)
    {
        return 1;
    }
    else if (number == 0)
    {
        return 0;
    }
    int f1 = 0;
    int f2 = 1;
    int ret = 0;
    for (int i = 1; i <= number; ++i)
    {
        ret = f1 + f2;
        f1 = f2;
        f2 = ret;
    }
    return ret;
}

　　

3.2 题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

同上一个题，只不过，这次真的需要memo了

int jumpFloorII(int number)
{
    vector<int> memo(number + 1, 1);
    for (int i = 1; i <= number; ++i)
    {
        for (int j = 1; j < i; ++j)
        {
            memo[i] += memo[j];
        }
    }
    return memo[number];
}

　　

 3.3 题目

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

f(0)=0

f(1)=1

f(2)=f(0)+f(1)

在于怎么铺，只有一个的时候，只有一种铺法。当连个2*1的时候，就有横竖两种了。因此，嗯，借用了上一个的状态。

int rectCover(int number)
{
    if (number == 1)
    {
        return 1;
    }
    else if (number == 0)
    {
        return 0;
    }
    int f1 = 0;
    int f2 = 1;
    int ret = 0;
    for (int i = 1; i <= number; ++i)
    {
        ret = f1 + f2;
        f1 = f2;
        f2 = ret;
    }
    return ret;
}