本文主要是介绍闲聊动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 什么是动态规划？
动态规划是一种用空间换时间的算法。就是把重复计算的过程得到的结果给存起来，以后再计算的时候发现存储的值，就不计算。
比如：力扣509题 的 斐波那契公式
package code04.动态规划专项训练01;/*** 斐波那契数* 力扣509* https://leetcode.cn/problems/fibonacci-number/description/?envType=study-plan-v2&envId=dynamic-programming*/
public class Fn_02 {public int fib(int n) {if (n <= 1) {return n == 1 ? 1 : 0;}if (n == 2) {return 2;}return fib(n-1) + fib(n-2);}public int fib2(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}int[] dp = new int[n+1];dp[1] = 1;dp[2] = 2;for (int i = 2; i <= n; i++) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
}
2. 什么是状态转移
上面的斐波那契公式，在递归中存在 return fib(n-1) + fib(n-2)。而在动态规划的代码中替换成了dp[i] = dp[i-1] + dp[i-2]; 这就是状态转移
之前是依赖下一次的计算结果的，而现在是依赖表格的前面列了的值了。
3. 动态规划有哪些固定的模板吗？
动态规划存在一些固定的模型的，因为动态规划根据递归改成动态规划的代码。通常，分为从左往右尝试模型、范围模型、样本模型、业务限定模型。
从左往右尝试模型： ，
范围模型： 最长回文子串 我写过博客
样本模型: 两个字符串找公共子序列 我写过博客
业务限定模型： 这种模型，其实就是根据不同业务去写一些奇奇怪怪的动态规划，比如最大正方形面积，机器人移动问题，勉强也能算业务限定模型。 我写过博客
当然，这些只是我接触过的，肯定还有很多是我没接触过的。因此，无法全部总结出来
4. 动态规划优势
动态规划最直接的优势就是空间换时间。其实，就是速度快。
5. 动态规划的优化方式有哪些？
斜率优化，严格表依赖、四边形不等式等等。针对枚举行为，动态规划可以使时间复杂度降低一阶。从算法30 到 算法33. 这几篇博客都是从左往右尝试模型。其中，其中有几篇涉及到枚举行为，更是实现了时间复杂度的降阶。
未完待续.....
这篇关于闲聊动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
