dp第一天

「动态规划」 – 学习计划 – 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

dp简单题，第一道永远是斐波那契数列

509. 斐波那契数

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

 F(0) = 0，F(1) = 1
 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
 给定 n ，请计算 F(n) 。



 示例 1：

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

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

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


 提示：

 0 <= n <= 30


 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/fibonacci-number
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 * @author zeroheart
 *
 */
public class Question509 {
    public int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 1;

        int[] r = new int[n+1];
        r[0] = 0;
        r[1] = 1;
        r[2] = 1;
        for(int i=3; i<=n; i++){
            r[i] = r[i-1] + r[i-2];
        }
        return r[n];
    }
}

这个题目中已经把转移方程写出来了，直接嵌套就行。F(n) = F(n – 1) + F(n – 2)

1137. 第 N 个泰波那契数

/**
 1137. 第 N 个泰波那契数
 泰波那契序列 Tn 定义如下：

 T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。



 示例 1：

 输入：n = 4
 输出：4
 解释：
 T_3 = 0 + 1 + 1 = 2
 T_4 = 1 + 1 + 2 = 4
 示例 2：

 输入：n = 25
 输出：1389537


 提示：

 0 <= n <= 37
 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

 * @author zeroheart
 *
 */
public class Question1137 {
    public int tribonacci(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 1;
        int[] r = new int[n+1];
        r[0] = 0;
        r[1] = 1;
        r[2] = 1;
        for(int i = 0; i <= n-3; i++){
            r[i+3] = r[i] + r[i+1] + r[i+2];
        }
        return r[n];
    }
}

本题也是最简单的类型，公式已给出Tn+3 = Tn + Tn+1 + Tn+2