动态规划课堂1-----斐波那契数列模型

目录

动态规划的概念：

动态规划的解法流程：

题目: 第 N 个泰波那契数

解法（动态规划）

代码：

优化：

题目：最小花费爬楼梯

解法（动态规划）

解法1：

解法2：

题目：解码方法

解法（动态规划）

结语：

---

动态规划：斐波那契数列模型

动态规划的概念：

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

动态规划的解法流程：

1.状态表示

dp问题的基础，自己要确定dp表每一个下标值的含义，这是用动态规划解决问题的第一步，只有把这一步确定了再去推出下面的状态转移方程，第一第二步完成后那么dp问题就已经解决了99%因为剩下的345就是处理边界和一些细节问题。

2.状态转移方程

推出状态转移方程可以说是dp问题最难的一步，如果在选定的状态表示下推不出状态转移方程，那么可能要换一个状态表示，因为状态表示可能是错误的。

3.初始化

一般初始化dp[0]和dp[1] .

4.填表顺序

一般有从左向右和从右先左，这取决于题目（覆盖问题）。

5.返回值

最后的返回值（不一定是dp[n]）.

由于是算法只讲知识点是远远不够的，故下面我会用例题来帮助大家理解（例题的链接会在最后给出）。

到这一些基本概念就讲解完毕下面开始用题目要带友友更加深入学习。

题目: 第 N 个泰波那契数

题目链接1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下： 

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

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

解法（动态规划）

1. 状态表示：

根据题目来推出状态表示，后面的大部分题目是要经验+题目来推出的

这道题可以「根据题目的要求」直接定义出状态表示：

dp[i] 表示：第i 个泰波那契数的值。

2.状态转移方程

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。

3.初始化

从我们的递推公式可以看出， dp[i] 在 i = 0 以及i = 1 的时候是没有办法进行推导的，因 为dp[-2] 或dp[-1] 不是⼀个有效的数据。因此我们需要在填表之前，将0, 1, 2 位置的值初始化。题目中已经告诉我们dp[0] = 0, dp[1] = dp[2] = 1 。（处理一些边界问题）

4.填表顺序

毫无疑问是「从左往右」。

5.返回值：

应该返回dp[n] 的值。

代码：

dp问题的代码编写流程一般比较固定分为1.创建dp表,2.初始化,3.填表,4.返回值.

最上面两个if用来解决边界问题。

class Solution {
    public int tribonacci(int n) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        int[] dp = new int[n + 1];
        if(n == 0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        dp[0] = 0;dp[2] = dp[1] = 1;
        for(int i = 3;i