动态规划

• 第十四届蓝桥杯省赛冲刺营【第二期】 - 【课后练习】小明的背包 1 - 蓝桥云课 (lanqiao.cn)

DP的两个特征

（1）重叠子问题。子问题是原大问题的小版本，计算步骤完全一样；计算大问题的时候，需要多次重复计算小问题。一个子问题的多次计算，耗费了大量时间。用DP处理重叠子问题，每个子问题只需要计算一次，从而避免了重复计算，这就是DP效率高的原因。

（2）最优子结构。首先，大问题的最优解包含小问题的最优解；其次，可以通过小问题的最优解推导出大问题的最优解。

能采用动态规划求解的问题的性质

最优化原理：

如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

无后效性：

即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

有重叠子问题：

即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势)

DP：记忆化

• 如果各个子问题不是独立的，如果能够保存已经解决的子问题的答案，在需要的时候再找出已求得的答案，可以避免大量的重复计算。

• 基本思路：用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。

• 记忆化

DP解题步骤

• 拆分问题

• 定义状态（并找出初状态）

• 状态转移方程

一般的模型方法

• 递归搜索法

• 记忆化搜索（记忆化暴力）

• 递推式法

空间优化：滚动数组

滚动数组：即只需要定义dp[2][j]：用dp[0][]和dp[1][]交替滚动。

空间优化：自我滚动

自我滚动：dp[j]=dp[j-c[i]]+w[i]即可。

根据背包是否要装满的初始化细节

• 装满：dp[0] = 0， 其余赋值为-INF；

• 不装满：memset(dp, 0, sizeof(dp))，全部初始化为0；

若一定要求装满:

•则必有n=sum(c[i]) i∈(已选集合)

•所以dp[n-sum(c[i])]= dp[0]

•所以只有从dp[0]出发才合法，那就把其他的设成无穷小。

动规练习题

李白打酒加强版2114 数组切分2148 积木画2110

分果果1459 括号序列1456 采药563

开心的金明554 传球游戏525 摆花389

最优包含239 画廊1032 蓝肽子序列1030

质数行者1027 游园安排1024 矩阵计数246

货币系统331 凑硬币1082 方格取数803

合唱队形742 纪念品786。