参考资料
动态规划之背包问题系列
背包九讲----整理+例题
背包问题常见的有三个问法：
- 求最大价值/最小代价：f[i][v]表示前i个物品中，放入容量为v的背包中最大价值
- 求是否刚好能凑出：f[i][v]表示前i个物品中，是否刚好能装满容量为v的背包
- 求方案总数：f[i][v]表示前i个物品中，装满容量为v的背包的方案总数
518. 零钱兑换 II
面试题 08.11. 硬币
这个题解最后有背包列表
完全背包和多重背包的二进制优化是什么?
8.16 第一章
什么题型可以用dp
- 动态规划可以解决三类问题
- 求最值 （最大、最小）
- 求方案数
- 求可行性问题
dp类问题肯定包含上面三个提问之一，但有上面问题之一不一定就是dp问题
- 如果一个数组满足不可交换时（具有方向性），是dp的信号之一（不是绝对的）
题面
坐标型
dp[坐标] = 行走到这个坐标的最优值
特点：状态使用dp(坐标)，如果是二维的，就用二维坐标表示，如果是一维就用一维坐标表示
状态转移：关心从哪一个坐标跳过来的
dp[i] = max(dp[i-1], max(dp[0]...dp[i-2]) + a[i]))
增加一个状态进行优化，第二维1表示打劫或者0表示不打劫
把决策（打劫或不打劫）记录到状态中去
这就很像买卖股票，买或不买了
dp[i][0] = max(dp[i-1][0], dp[i-1][1])
dp[i][1] = dp[i-1][0] + a[i]
不用往回推了吗，跟0 ~ i-2的状态没有关系了吗
难以理解
前缀型
dp[i] = 前i个数的最优值
特点： 前缀表示状态，如看前i个数取出的最大和，不关心第i个数取或者不取
dp[i] = max(dp[i-1], dp[i-2]+a[i])
8.16 第二章
背包型
- 0/1背包
f[i][j]表示前i个物品，j是和为j，是一堆数为和
dp[i][j] 骰i次骰子和为j的概率
影响概率的是骰子的个数、骰子点数的和，这两个都是变数，放到状态里考虑，所以状态是2维
8.16 第三章
后缀型（和前缀型一样）
dp[i]表示i ~ len-1 中，以i开始的最长有效括号长度
8.19 第四章
直方图最大矩阵
单调栈
每次将栈中比当前数据大的弹出，最后栈中剩下的数据压入一个0来弹出
8.22 第五章
假期
公司给小q放了n天假，小q打算在假期中工作、锻炼、休息，他有个奇怪的习惯，不会连续两天工作或锻炼。
只有公司营业时，才去工作，只有健身房营业时，采取锻炼。给出公司、健身房营业情况，计算出小q至少要休息几天？
一个线索是决策当前去做什么事情，只与前一天的情况有关，跟之后、更前 都没有关系，这种很容易想到是dp
输入：
放假天数 4
公司营业 1 1 0 0
健身营业 0 1 1 0
输出： 2
j : 0 工作 1 锻炼 2 休息
dp[i][j] 表示第i天做j这个事情，最小的休息天数
滚动数组 dp[i%2]
相关题目
买卖股票
8.22 第6章
1049. 最后一块石头的重量 II
给定一组石头，每个石头有一个正数的重量，每轮开始时，选择两个石头进行碰撞。假定两个石头的重量为x, y, x<=y，碰撞结果为
- 如果x == y,两个石头消失
- x!=y，两个石头消失并生成一个新石头重量为|x-y|
最后最多剩一个石头结束，求最小的剩余石头重量
输入：
石头个数
石头重量，空格分开
背包型dp与数组中数据顺序无关、与方向无关
本题可以转为01背包
背包问题要再看下 01背包、完全背包、混合背包
8.22 第7章
1000. 合并石头的最低成本 类似
312. 戳气球
有n堆金币排成一排，第i堆有c[i]块金币。每次合并都将相邻的两堆金币合并为一堆，成本为两堆金币之和。最终合并为一堆，请计算合并为一堆的最低成本。
区间型动态规划
dp[i][j] 表示第i堆到第j堆合并的最小代价
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[i][j])
sum[i][j]表示i到j的和，可以用前缀和来实现
大区间依赖小区间，注意两层循环实现问题
研究最后一步要做啥 反向推，自顶向下的分治方法
8.22 第8章
字节 毕业旅行 traveling-salesman-problem
状态压缩dp
8.22 第9章
美团：外卖满减
n个菜，价格为prices[i]，要选到x元，至少话费多少元
应用反选法，
01背包能不能凑出某个和
这里涉及到选数求和的问题，一般是背包型动态规划。
8.22 第10章
256. 粉刷房子
坐标型
8.22 第11章
最大子数组差 maximum-subarray-difference
给一个整数数组，找出两个不重叠子数组a和b，使两个子数组和的差的绝对值最大 |sum(a) - sum(b)|
相似题目 lintcode 1833 钢笔盒 1850 捡苹果
8.22 第12章
求方案总数、可行性 99%就是dp，求最大最小还不一定
双色塔 two-colors-tower
取模运算
(a + b) / c = (a %c + b %c ) %c
加 减 乘 都满足
区间不重叠，考虑隔板法