动态规划引入

概念：

动态规划将一个复杂的问题分解为一系列相互关联的子问题，通过求解这些子问题，并利用子问题的解来构造原问题的解。它通常使用一个表格或数组来存储子问题的解，这样可以避免在求解过程中对同一个子问题进行多次重复计算，从而提高算法的效率。

解题步骤：

一.解析题目

二.算法原理:1.状态表示2.状态转移方程3.初始化4.填表顺序5.返回值

三.编写代码

四.空间优化

 动态规划简单来说就是创建一个一维数组或者二维数组，里面存的每一个值都表示一种状态

这些状态怎么来的：1.根据题目  2.经验+题目要求   3.分析题目的过程中发现重复的子问题，把子问题抽象成一种状态

 以一道入门级动态规划题目进行讲解leetcode1137

一。解析题目：读题，看题目要求 

二。算法分析第一步状态表示：创建一个一维数组dp，dp[i]表示：第i个泰波纳契数 

算法分析第二步状态转移方程：由题目可得dp[i]=dp[i-1]+dp[i-2]+dp[i-3];（也就是求dp[i]=什么）

算法分析第三步初始化：保证填表得时候不越界，也就是这里得第0/1/2个需要你手动初始化

                                       有状态转移方程是得不到0/1/2的

算法分析第四步填表顺序：为了填写当前状态，所需要的状态已经计算过了，例如你在求第四个位置时，1/2/3的位置已经计算出来了，而不是跳过计算第3个位置，去算第4个然后填第四个，所以你填表的顺序是从左到右

算法分析第五步返回值：返回值要根据题目要求+你的状态表示，题目要求返回第n个泰波纳契数，你的状态表示为dp[i]:i表示第i个泰波纳契数，所以直接但会dp[i]即可

三。编写代码：

四。空间优化

1.滚动数组：可以观察当我们在解决第i个状态时，只要用到前若干个，也就是这里我们填第4个状态时，只要1/2/3，填第5个是只要2/3/4，所以我们可以不用管其他状态的值

这样空间复杂度就变为O(1);

 

注意这里的赋值操作：从前往后赋值和从后往前赋值不同，从后往前在这里是错误的 ，也就是你不能c=d，b=c，a=b；

总结

动态规划的题目大致解决方法都可以按照如上的思路进行