动态规划求解完全背包问题
动态规划基本原理？
动态规划基本原理？
动态规划是运筹学的一个分支，是求解决策过程最优化的过程。
20世纪50年代初，美国数学家贝尔曼等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。
动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域；
并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。
动态规划基本原理？
动态规划的基本原理
能用动态规划解决的问题的特点
问题具有最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。
无后效性：当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取那种手段、哪条路径演变到当前的这若干个状态无关。事实上，不满足无后效性的问题分解是写不出状态转移方程的。不过这也与我们分划问题涉及状态的艺术有关。
动态规划解题的一般思路
将原问题分解为n个子问题：将原问题分解为若干个子问题，子问题和原问题形式相同或者类似，只不过规模变小。当子问题全都解决时，原问题即解决。子问题的解一旦求出就被保存，所以每个子问题只需要求解一次。
确定状态：用动态规划解题，经常碰到的情况是，K个整形变量能构成一个状态，我们用一个K维的数组来存储各个状态的值。注意这里的值并不一定是一个数，而可能是结构体等。一个状态下的值通常是一个或者多个子问题的解
确定一些初始状态（边界条件）的值
如果使用记忆化搜索，即设置递归出口，
如果使用递推，就需要将这些值填入dp数组
确定状态转移方程：求出不同状态之间是如何迁移的，即如何从一个或者多个值已知的状态，求出另一个状态的值。状态的迁移通常可以用递推公式表示，该公式就是状态迁移方程。
具体实现
记忆化搜索
直接按照递归函数的思路完成编写，只是在函数的头部增加快捷返回出口，函数return前存储值。
dp数组：递归函数有n个参数，就定义一个n维的数组，数组的下标最大值是递归函数参数的取值范围
也就是说，我们把每一种参数对应的值都开一个空间存起来。
递推
根据我们的递推公式来判断循环递推的方向。如果递推公式涉及的元素是不断增大的，那么就从小开始递推不断增大，反之则从大开始不断减小
比如 d p [ r ] [ j ] = m a x ( d p [ r 1 ] [ j ] , d p [ r 1 ] [ j 1 ] ) n u m [ r ] [ j ] dp[r][j] = max(dp[r 1] [j], dp[r 1] [j 1]) num[r] [j]dp[r][j]=max(dp[r 1][j],dp[r 1][j 1]) num[r][j]
这个递推公式涉及的元素r、j都不断增大，那么我们就应该从小到大递推
确定递推的边界条件。最初始的一些值我们需要提前在dp数组中初始化好，同时还要设置一些递推的非法出口的值。非法出口的设置需要保证：永远不可能用到这个出口来更新某个dp，故而我们应使用反向意义来设置非法出口
非法出口类同于递归中出现超出范围、显然不再可能可以完成任务的参数的情况的return
反向意义：例如我们求最小值，非法出口就应定义为99999999
在递推中，当我们在求d p [ r ] [ j ] dp[r][j]dp[r][j]时，我们必须已经求出了所有r、j之前的dp值，故而判断递推的方向和边界条件非常重要
用一个N层循环来递推，N为dp数组的维数，从边界值开始，逐步填充数组，前一个阶段的解，为后阶段的求解提供有用的信息
使用递推的时候虽然快，但是要考虑的东西却很多很多，有一些局部细节和临界条件的考虑非常重要，有时候记忆化搜索能AC递推却WA就是因为有一些极限情况没有考虑到