一、什么是动态规划?
- 动态规划(Dynamic Programming,简称Dp) 是
一种算法思想
: 将原(大)问题化解成子问题,再根据子问题的解得出原问题的解;
1.1 、什么是最优子结构和重复子问题?
1.2、什么是状态转移方程,跟最优子结构的关系?
状态转移方程:是一种组合关系,描述了一种原问题与子问题的组合关系
PS: 看着描述和最优子结构问题的描述一样,其实就是一样,一个是文字描述,一个数学表达
例如:f(n) = f(n - 1) + f(n - 2)f(n)=f(n−1)+f(n−2)
1.3、什么是动态规划的核心?
核心:找最优子结构,也就是找状态转移方程
1.4、什么是动态规划问题的难点?
- 如何定义
f(n)
: 定义原问题的解 - 如何定义
状态转移方程:
如何通过 f(1)f(1), f(2)f(2), … f(n - 1)f(n−1) 推导出 f(n)f(n),即状态转移方程
1.5、动态规划的两种解决思路
- 自顶向下:递归方法+记忆化搜索
- 自底向上:从最小的问题规模入手,然后不断地增加问题规模,直到所要求的问题规模为止。
二、动态规划(dp)、贪心、回溯、分治算法的联系?
-
划分为2类:贪心、回溯、动态规划可以归为一类,而分治单独可以作为一类文章来源:https://www.toymoban.com/news/detail-477046.html
-
回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题,都可以用回溯算法解决。回溯算法相当于穷举搜索。文章来源地址https://www.toymoban.com/news/detail-477046.html
到了这里,关于动态规划:什么是动态规划?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!