动态规划解题步骤:首先动态规划的题目主要的目的是为了填写表dp中的空缺部分。1. 状态表示就是要填写到qp表中那个值的涵义。2. 状态转移方程就是dp[i]值怎么得到的。3. 初始化初始化一些值防止在执行状态方程的时候出现下标越界。4. 填表顺序根据合顺序的到dp[i]确保下一个值所需要的条件已经得到。5. 返回·值返回题目所需要的结果。1. 第N的泰波那契数1.1 题目解析由题可得当一个数列长度大于等于3的情况下满足当前数的值等于前三个数之和要求得到第N个数的值前三个数分别等于0、1、1。1.2 解题思路通过动态规划的解题步骤状态表示为第i个泰波那契数的值状态转移方程为dp[i] dp[i-3] dp[i-2] dp[i-1]初始化为 dp[0] 0,dp[1] dp[2] 1填表顺序从下标小的到下标大的从左向右返回值第N个下表对应的值。首先我们要先判断所给n的值当n大于等于3时我们可以通过一个fori循环初始化i3、in直接的到结果。1.3 代码实现优化后:1.4 复杂度时间复杂度O(N)空间复杂度: O(N)优化后时间复杂度O(N)空间复杂度: O(1)