动态规划
其思想与分治法类似,是将待求解问题分为若干个小问题
通过局部最优求出全局最优
动态规划类问题主要的求解步骤:
1. 划分阶段 斐波那契数列的每一项作为一个阶段
2. 确定状态 第iii项的值用第iii位表示a[i]a[i]a[i]
3. 确定决策并写出状态转移方程式 每一项的值都是前两项的和a[i]=a[i−1]+a[i+2]a[i] = a[i - 1] + a[i + 2]a[i]=a[i−1]+a[i+2]
结尾法:dp[i]dp[i]dp[i]就表示以下标iii结尾的答案
性质
1. 最优化原理:(最优子结构)
* 如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理
2. 无后效性:
* 即某一阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
3. 子问题重叠:
* 即子问题之间是不独立的,一个子问题在下一阶段决策中可能多次被使用到。(该性质并不知动态规划适用的必要条件,但是如果没有这条性质,动态规划算法问题同其他算法相比就不具备优势)
前缀法
dp[i]dp[i]dp[i] 表示 1 i1~i1 i 处理完毕的结果,dp[n]dp[n]dp[n] 就是答案
有向无环图
背包
0/1背包
想象一个容量为VVV的背包,你需要在KKK个物品中选择一些物品转入,每个物品只有装/不装两个状态,并且每个物品占用空间为viv_ivi ,价值为wiw_iwi ,求不超过容量VVV能装进物品的最大价值
我们设dp[i][j]dp[i][j]dp[i][j]表示在前iii个物品中已经选好了最佳方案,并且容量不超过jjj时,所能获取的最大值
对于iii物品,如果选择不装入,则有dp[i][j]=dp[i−1][j]dp[i][j]=dp[i - 1][j]dp[i][j]=dp[i−1][j](继承之前的状态)
如歌选择装入,则有dp[i][j]=dp[i−1][j−v[i]]+w[i]dp[i][j]=dp[i - 1][j - v[i]] + w[i]dp[i][j]=dp[i−1][j−v[i]]+w[i](表示拿这个物品,占用对应背包空间,并且获取对应价值)
两者取最大,则有dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i])dp[i][j]=max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i])
滚动数组
压缩为1维
无限背包
想象一个容量为VVV的背包,你需要在KKK个物品中选择一些物品转入,每个物品可以任意选个数,并且每个物品占用空间为viv_ivi ,价值为wiw_iwi ,求不超过容量VVV能装进物品的最大价值
我们设dp[i][j]dp[i][j]dp[i][j]表示在前iii个物品中已经选好了最佳方案,并且容量不超过jjj时,所能获取的最大值
对于iii物品,如果选择不装入,则有dp[i][j]=dp[i−1][j]dp[i][j]=dp[i - 1][j]dp[i][j]=dp[i−1][j](继承之前的状态)
如歌选择装入,则有dp[i][j]=dp[i][j−v[i]]+w[i]dp[i][j]=dp[i][j - v[i]] + w[i]dp[i][j]=dp[i][j−v[i]]+w[i](表示拿这个物品,占用对应背包空间,并且获取对应价值)
两者取最大,则有dp[i][j]=max(dp[i−1][j],dp[i][j−v[i]]+w[i])dp[i][j]=max(dp[i - 1][j], dp[i][j - v[i]] + w[i])dp[i][j]=max(dp[i−1][j],dp[i][j−v[i]]+w[i])(注意j的循环一定要从小到大)
一维
任务
1. 完成题目时间 黄题20min 绿题40min 蓝题100min
2. 手搓3组数据
3. 每次提交WA之后 记录WA的原因