leetcode第509题，斐波那契数。一般可以直接使用循环或者递归的方式(类似一维DP数组)，这里采用动态规划来完成。

LeetCode 509斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1F(0) = 0，F(1) = 1
2F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

1输入：n = 2
2输出：1
3解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

1输入：n = 3
2输出：2
3解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

1输入：n = 4
2输出：3
3解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

  • 0 <= n <= 30

思路

这道题可以用循环或者是递归的方式。

但是也可以通过动态规划来操作，如何构建一个让前面的状态去影响后面的状态的动态规划数组（DP）。

1F(n) = F(n - 1) + F(n - 2);//其中n > 1

解题

 1class Solution {
 2    public int fib(int n) {
 3        //动态规划的方式
 4        if(n <= 1)
 5        {
 6            return n;
 7        }
 8        int[] DP = new int[n + 1];
 9        DP[0] = 0;
10        DP[1] = 1;
11        for(int i = 2; i < n + 1; i++)
12        {
13            DP[i] = DP[i - 1] + DP[i - 2];
14        }
15        return DP[n];
16    }
17}