动态规划总结（入门）

动态规划Dynamic programming
先举一道例题做引入：
有一个最多能装m公斤的背包，现在有n中物品，每件的重量分别是W1、W2、……、Wn，每件物品的价值分别为V1、V2、……、Cn， 需要将物品放入背包中，要怎么样放才能保证背包中物品的总价值最大？

适合用动态规划解决的问题一般包含3个性质：

① 最优化原理：如果问题的最优解包含的子问题的解也是最优的，就称该问题具有最有子结构，即满足最优化原理。
② 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
③ 重叠子问题：进行决策后产生的子问题并不总是新问题，一个子问题在下一阶段决策中可能被多次使用到。

利用动态规划解题的一般步骤：

0.啊哈，就是写状态转移方程，然后循环实现就完事儿了
1.确定状态：确定状态即确定解决问题时某一步的，简单来说就是我们写状态转移方程时候开的数组f[i]。
2.
3.
4.

坐标型动态规划

序列型动态规划

划分型动态规划

区间型动态规划

博弈型动态规划

位操作型动态规划

背包型动态规划

双序列型动态规划

【算法学习】动态规划

原文：https://www.cnblogs.com/muscletear/p/14370179.html