ORID46

今天学习了区间型动态规划

• 给定一个序列/字符串，进行一些操作
• 最后一步会将序列/字符串去头/尾
• 剩下的会是一个区间[i, j]
• 状态自然定义为f[i][j], 表示面对子序列[i, ..., j] 时的最有选择

474. Ones and Zeroes

最后一步：最优策略组成了最多的01串，其中有没有最后一个字符串S_t-1。
情况一：没有S_t-1。

• 需要知道前T-1个01串中，用m个0和n个1最多能组成多少个01串

情况2:有S_t-1

• 设第T-1个01串中有at-1个0，bt-1个1
• 需要知道前t-1个01串中，用m-at-1个0和n-bt-1个1 最多能组成多少个01串

lintcode 89. k Sum 解题报告

用什么算法？

DP，这道题的核心思想是背包问题
题目要求是从一些正整数中选出一些，使得和是target
数组A（给你的数组） 就相当于每个物品的重量
target就是背包的最大承重，目标就是要背包正好装满
动归组成部分一：确定状态
最后一步：最后一个数An-1 是否选入这k个数
情况一（An-1不选入）：需要在前n-1个数中选k个数，使得它们的和是target
情况二（An-1 选入）：需要在前n-1个数中选k-1个数，使得他们的和是target - An-1
要知道还有几个数可选，以及他们的和需要是多少：序列加状态
状态：f[i][k][s] 表示有多少种方法可以在前i个数中选出k个，使得他们的和是s
动归组成部分二：公式转化
f[i][k][s] = f[i-1][k][s] + f[i-1][k-1][s-Ai-1] | s>=Ai-1
这里的公式转化就是说有多少种方法可以在前i-1个数中选出k个，使得他们的和是s
再加上有多少种方法可以在前i-1个数中选出k-1个，使得他们的和是s-Ai-1

动归组成部分三：初始条件和边界情况
f[i][k][s]表示有多少种方法可以在前i个数中选出k个，使得它们的和是s
初始条件：
f[0][0][0] = 1
f[0][0][s] = 0 s 从 1 到 target
边界条件：
如果s<Ai-1, 只考虑情况一，因为你凑不出target