一个，
意识形态框架
想法：
用空间换时间。
首先我们不看动态规划法，先了解递归法。递归方法的逻辑很简单。“要解决父母的问题，首先要解决孩子的问题，而要解决孩子的问题。”但是当有两个以上的子问题时，可能会调用同一个孙子问题，会无故浪费时间，多次调用会造成浪费。因此，动态规划方法应运而生。解决这种时间浪费的方法如下：
把解决的问题保存下来，每次遇到直接打电话，这样就省去了很多重复。
这就是动态规划中“以空间换时间”思想的由来。
其次，
三个主要步骤
解决这个动态规划问题有三个常见的步骤
一个
为了建立状态数组dp，动态规划的一般思想是状态。当您处于任何状态时，对应的数组f[i][j]存储该状态。而且这一步也很关键。只有当我们能够理解“状态”的概念时，我们才能使用状态转移方程。
2
状态转移方程的一般形式写成数组的形式。以《数字三角形》 [2]为例，该问题的状态转移方程为dp[i][j]=(dp[i，j]，dp[i 1，j] a[i])
对状态转移方程的理解是：
前一个问题dp[i][j]会对后一个问题产生什么影响？每个状态的数学表示可以用三个参数z，I和J表示为z=dp[i][j].这三个参数z代表这个状态的大小。I一般代表这个状态的序号，j一般代表这个状态的条件。
影响“状态”数组的因素有两个。一个是之前的状态，没什么好说的。递归总是这样。二是状态转换的“成本”，成本一般是我们一开始投入的东西，比如爬楼梯需要的高度，摘苹果需要的体力等等。
三
循环，因为整个状态数组构造过程需要经过一个遍历过程(遍历I变量)。而在这个过程中，每个状态都有很多可能性(J变量的遍历)，所以确定遍历是第三个关键点。确定了这三个关键点，就可以确定整个核心算法。
三大要素
成本数组a[N]
//存储所有成本
状态数组dp[N][M]//存储每个状态
状态转移方程f(dp)//的一般表达式是：这个状态=f(这个状态或前一个状态代价)f是某个状态的选择方式，比如最小或最大
相关阅读
标签： #动态规划最新问题
