DP动态规划算法理解

学习了DP动态规划算法，对动态规划也有了一点理解，动态规划是将原来的一个大问题分解为一个简单的子问题，找到子问题的答案，再通过子问题与原问题的关系找出原问题的答案。动态规划算法对每个子问题只求解一次，将其结果保存起来，从而避免每次遇到各个子问题重新计算。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

本次练习中最多的问题就是背包问题，背包问题分为01背包、完全背包和多重背包，01背包是n件物品每个物品只能装一次，使得m的容积所装的价值最大，可以开一维的dp数组也可以开二维的dp数组，二维dp数组dp[i][j]存储的是i件物品当背包所剩空间为j时所能装的最大价值利用双重循环更新dp数组的最大值当j<v[i]，背包空间小于第i件物品的体积时，dp[i][j]=dp[i-1][j]；当j>=v[j]时dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])；而一维数组是将背包空间倒着查找，外层循环为1~n件物品背包空间倒着查到v[i]就进行下一轮循环，dp[j]=max(dp[j],dp[j-v[i]]+w[i])；一维数组dp存储的是当背包空间剩余j时共n件能装的最大价值。相对于二维数组一维数组更加节省空间。https://blog.csdn.net/kongsanjin/article/details/81359197

完全背包是有n种物品每种物品都可以无限次的装，还是使得容积为m的背包所装的价值最大，完全背包的实现只要将背包的空间进行正着查找就行了，这样就会当装上物品能使背包的价值更大，就会再次装上此物品，使得背包价值更大。（这是一个完全背包只不过控制条件多了）https://blog.csdn.net/kongsanjin/article/details/81359573

而多重背包就是有n种物品，给出每种物品的体积，价值和数量，如何让背包里装入的物品具有最大的价值总和？其实和01背包是一样的，只不过是每种物品的数量可能不同，也可以看成01背包来做，把所有的物品总数求出来，按01背包二维数组来做，也可以用一维数组外层两个循环，控制种类和数量。https://blog.csdn.net/kongsanjin/article/details/81358717

我认为动态规划的问题还是要具体情况具体分析了，一般都是要先将原问题分解成子问题，再确定状态，确定初始状态和边界的值，找出状态转移方程。