0、概念
0.1 定义：
** 动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。。
0.2 核心思想：
动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。
0.3 适用范围：
什么样的题目适合动态规划？ 如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。
动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法，常见的分类如下，具体啥含义可以自行查询：动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
1、线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
2、区域动规：石子合并，加分二叉树，统计单词个数，炮兵布阵等；
3、树形动规：贪吃的九头龙，二分查找书，聚会的欢乐，数字三角形等；
4、背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶等；
5、应用实例：最短路径问题，项目管理，网络流优化等。
0.4 基本步骤：
动态规划的核心思想就是拆分子问题，记住过往，减少重复计算。 并且动态规划一般都是自底向上的，动态规划的大致思路：
- 穷举分析
- 确定边界
- 找出规律，确定最优子结构
- 写出状态转移方程
1、例子
问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法？
这个问题乍一看无从分析，但是穷举是可以的，我们倒着推要想：
1、跳到第10级台阶，要么是先跳到第9级，然后再跳1级台阶上去;要么是先跳到第8级，然后一次迈2级台阶上去。
同理，要想跳到第9级台阶，要么是先跳到第8级，然后再跳1级台阶上去;要么是先跳到第7级，然后一次迈2级台阶上去。
要想跳到第8级台阶，要么是先跳到第7级，然后再跳1级台阶上去;要么是先跳到第6级，然后一次迈2级台阶上去。
…
化成数学公式
f（10） = f（9）+f(8)
f (9) = f(8) + f(7)
f (8) = f(7) + f(6)
...
f(3) = f(2) + f(1)
即通用公式为: f(n) = f(n-1) + f(n-2)
1.1、解法一：递归
//伪代码
int recursion (int n) {
if(n == 1){ return 1;}
if(n == 2){ return 2;}
return recursion (n-1) + recursion (n-2);
}
递归算法有缺点，当这个n很大时候，那么系统开销很大，因为要调用的层级太多，系统保存的量很大，而起很多是重复量，优化代码如下
1.2、解法二：带记录的递归
//伪代码
//用map保存计算过程量，作为备忘录
Map<Integer, Integer> recordMap = new HashMap();
int recursion (int n) {
if(n == 1){ return 1;}
if(n == 2){ return 2;}
//先判断有没计算过，即看看备忘录有没有
if (recordMap.containsKey(n)) {return recordMap.get(n);}
else {
// 备忘录没有，即没有计算过，执行递归计算,并且把结果保存到备忘录map中
recordMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007); //防止越界
return recordMap.get(n);}
}
1.3、解法三：动态规划
动态规划其实包含上述递归的思想，但是和带记录的递归不一样的是，递归是自上而下的，动态规划是自下而上的，取得局部最优解在往上去取得上层最优解，并且局部最优解不受上层影响。
//伪代码
int numWays(int n) {
if (n<= 1) {return 1;}
if (n == 2) {return 2;}
int a = 1,b = 2;;
int temp = 0;
for (int i = 3; i <= n; i++)
{
temp = (a + b)% 1000000007;
a = b;
b = temp;
}
return temp;
}
2、总结
对应0的解题步骤，结合1的实例可以看出主要步骤
-
穷举分析：
首先对于问题，我们一步步分析其中规律，确定该问题是不是该
问题穷举法完成，不管其复杂与否。 -
确定边界：
通过穷举分析，我们发现，当台阶数是1的时候或者2的时候，可 以明确知道青蛙跳法。f（1） =1，f(2) = 2，当台阶n>=3时，已经呈现出规律f(3) = f(2) + f(1) =3，因此f（1） =1，f(2) = 2就是青蛙跳阶的边界。 -
找出规律，确定最优子结构：
n>=3时，已经呈现出规律 f(n) = f(n-1) + f(n-2) ，因此，f(n-1)和f(n-2) 称为 f(n) 的最优子结构，关于最优子结构，我是这么理解的，就是可以用一个公式表示该问题的所有一般规律，并且是无记忆的。 -
写出状态转移方程：
f(n) = f(n-1) + f(n-2)
f（1） =1，f(2) = 2 -
代码实现一般模板：文章来源：https://www.toymoban.com/news/detail-495178.html
dp[0][0][...] = 边界值
for(状态1 ：所有状态1的值){
for(状态2 ：所有状态2的值){
for(...){
//状态转移方程
dp[状态1][状态2][...] = 求最值
}
}
}
3、引用
1、看一遍就理解：动态规划详解
2、算法-动态规划 Dynamic Programming–从菜鸟到老鸟
3、第9章 动态规划
4、动态规划的实际应用：图片压缩算法文章来源地址https://www.toymoban.com/news/detail-495178.html
到了这里，关于经典动态规划问题详解以及其主要应用场景的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[动态规划] 01背包问题及其优化](https://imgs.yssmx.com/Uploads/2024/02/776453-1.jpeg)
