闲聊动态规划

2024-03-08 04:20

文章标签 动态规划闲聊

本文主要是介绍闲聊动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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. 动态规划优势

动态规划最直接的优势就是空间换时间。其实，就是速度快。