开个帖子记录自己刷挑战程序竞赛的历程

加油加油加油

zzwcsong 发表于 2019-2-17 06:38
感谢楼主分享！

看到Github上有个repo ： https://github.com/yogykwan/acm-challenge-workbook

hha 我知道这个repo...想不出来的时候全靠它续命

铁汁加油

刷题 发表于 2019-2-17 15:45
铁汁加油

多谢老铁

继续之前先扯两句:
1. 挑战程序设计竞赛绝对不适合拿来准备工作。如果以迅速准备面试为目的效率最高的还是把lc各个专题的高频题刷个五六遍。
2. 这本书本身也有一定的缺陷，最大的问题在于讲的不够详细。对初学者不算不友好，还是适合见过一些常规套路之后再来做。
3. 做了别的OJ才明白 LC 是多么的温柔体贴，还把哪里出了错告诉你。Poj上一个wa又不知道哪里出了问题真是让人分分钟想跳楼（或者对题解）

动态规划

Dynamic Programming 的核心要点在于提取并且避免重复运算，下面通过几种经典套路来介绍其思想。

1. 背包相关

1.1  0/1 背包问题

n个价值为 wi, vi的物品，从这些物品中挑选总重量不超过 W 的物品，每个物品只能挑选一次，求最大值。

直接朴素解法，考虑到每个物品都有选以及不选两种选择，我们定义 rec(i, j) 为从第i个物品开始选择，总重小于j能获取的最大价值。那么核心的递归表达式是 rec(i, j) = max(rec(i+1, j), rec(i+1, j - w[ i ]) + v[ i ])， 复杂度为O(2^n)。

画出递归调用，可以发现经常有重复调用的情况，因此我们可以用一个dp矩阵把计算出的 rec(i, j) 记录下来。这样如果调用 rec(i, j)的时候发现 dp 里面已经有值了即可直接返回。时间复杂度取决于 (i, j) 组合状态总数，也即 O(nW)。这种方法也称记忆话搜索，如果不这么做当然我们也可以通过递推来做。

设dp[ i ][j] 为前i个物品，总重量不超过j的最大价值，那么有 dp[ i ][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]). 这里需要注意三点：

a. 定义是前i个物品，也就是编号 0 -> i-1的物品。这么定义的好处是方便处理边界值。因此需要注意dp的 size为 (n+1, W+1)
b. 初始化 dp[0][0] = 1, 其他 dp[x][0] = 0, dp[0][x] = 0, 原因显而易见
c. 返回 dp[n][W] 即可  

1.2. 0/1 背包问题大重量版本

一模一样的问题，不过限制为 1 <= n <= 100; 1 <= W <= 10^9, 1 <= vi <= 100, 1 <= n <= 100;

这里的问题在于W的范围太大，因此导致了 O(nW) 的复杂度过高。然而我们注意到物品的总价值不会超10000, 因此灵机一动（个鬼）的想到可以通过价值来限制重量。我们这么定义：dp[ i ][j]是前i个物品取到价值为j的最小重量。那么我们我们既可以在前i-1个物品中选价值为j的，或者在前i-1个物品中选价值为j-v[i-1]的，再选择第i-1个物品，这样可得：

dp[ i ][j] = min(dp[i-1][j], dp[i-1][j-v[i-1]] + w[i-1])

因为显然前0个物品的总价值只能为0，因此初始化为 dp[0][0] = 0, dp[0][x] = INF。最后返回最大的j使得dp[n][j] < INF 即可。这样的复杂度就变成了 O(nV), V为总重量。

1.3. 完全背包问题

和0/1背包相同，不过现在每个物品可以取无限多次。

dp[ i ][j] = max(dp[i-1][j], dp[ i ][j-w[i-1]] + v[i-1]) 即可。表明虽然第i-1个物品取过了，不过还可以再接着取。

顺便一说dp的空间复杂度优化。当dp[ i ][j]的结果只依赖于dp[i-1][j]的时候我们可以用1D array来记录状态。但是遍历j的时候需要从大往小遍历（否则会覆盖上一轮循环的结果）。当当dp[ i ][j]的结果只依赖与dp[i-1][j]的时候则还是从小往大遍历。

1.4. 多重部分和问题

给n种硬币，每种硬币个数为 C[ i ], 币值为 A[ i ], 问可否凑足总计为 m 的数额。

和背包类似的凑硬币问题(本质上就是 combination sum)，区别在于这里硬币的种类有限，并且每种给出了具体的数量。一种比较容易想到的思路是用 dp[ i ][j] 来表示前i种硬币凑面值为j的凑法，最后返回dp[n][m]。然而稍加分析发现这样做复杂度较高。因为dp[ i ][j] = dp[i-1][j] + dp[i-1][j - k*A[i-1]] for all j >= k*A[i-1]。最后需要写一个三重循环，复杂度是 O(m * sum(Ci))。

我们发现这里实际上只需要知道能不能凑，不需要知道具体的凑法。因此一个机智到爆的定义方法是用 dp[ i ][j] 来表示凑足 j 后第i-1种硬币最大的剩余个数 (-1 表示凑不满).　那么我们有

(1) if dp[ i ][j-1] >= 0 : dp[ i ][j] = C[i-1] 　　                    #  前i-1种硬币就足够凑满j了，第i-1个硬币可以全部剩下;
(2) if j > A[i-1] or dp[ i ][j - A[i-1]] <= 0: dp[ i ][j] = -1      #  剩下的硬币总数小于第i-1个硬币的面值，或者我们不能凑足 j的数这种情况显然不能满足要求;
(3) else: dp[ i ][j] = dp[ i ][j - A[i-1]] - 1                              #  我们只要先凑足j - A[j-1], 再取一个C[i-1]就好了。

初始化：dp[0][j] = 0, dp[ i ][0] = C[i-1], 含义很明确：如果需要凑足的面额为0，那所有硬币都能剩下来。最后如果只要有dp[n][m] != -1 则返回 true, 否则返回 false. 复杂度 O(nm).

PS: 这是楼教主男人八题里面的一道，果然不同凡响。。。

2. 字符串/数组相应问题

2.1. LCS 问题

给两个子串s, t, 求这两个子串最长公共子序列长度。

经典题目了，dp[ i ][j]定义为s[:i]和t[:j]的LCS, 随后我们有

if s[i-1] == t[j-1] : dp[ i ][j] = dp[ i ][j] + 1
if s[i-1] != t[j-1] : dp[ i ][j] = max(dp[i-1][j], dp[ i ][j-1])  # 分别对应不取s[i-1]和不取t[j-1]这两种情况

初始化的时候，dp[x][0] = 0, dp[0][x] = 0, 因为只要有一个字符串位0，公共子串长度一定位0. 最后返回 s[n][m], n, m 分别位 s, t 长度。

1.2. LIS 问题

最长上升子序列，给一个数列 A，问其中最长的严格递增的子序列长度。

也是经典老题了。

思路1: dp[ i ]定义为前i个字符。dp[ i ] = 1 + max(dp[j] | for all j < i and A[j-1] < A[i-1]),复杂度 O(N^2)

思路2：dp[ i ]定义为长度为i的LIS的最小末尾元素。首先dp所有元素定义为 INF。然后对每个A[j], 寻找最大的i使得dp[ i ] < A[j],更新dp[i+1] = min(dp[i+1], A[j])来减小长度为i+1的LIS的末尾元素即可。注意dp是递增的，这个过程可以用二分优化，复杂度可以做到 O(NlogN).

3. 计数问题

3.1.划分数

给两个数n, m, 问把n分成不超过m类有几种分法。比如 n=4, m=3则输出4，代表有4种分法：2+1+1, 3+1, 4, 2+2。

用dp[ i ][j]来表示j分成不超过i类的分法。一种思路是从j中先取k，然后再把j-k划分成i-1类，这样就成了 sum(dp[i-1][j-k]) for k = 0->j. 可惜这种做法是错误的。因为会把 1+2+1 和 2+1+1 分别计算成两种不同的结果，然而它们实际上是一种。

正确而诡异的思路是这样的：在分成的i类里，要么没有一个是0，要么至少有一个0，前者的话，我们把i类每个减去1，就可以把 j - i 分成i类的结果是一样的。因此对应dp[ i ][j-i], 第二种情况则对应dp[i-1][j], 相当于把j分成最多i-1份。因此dp[ i ][j] = dp[ i ][j-i] + dp[i-1][j].

初始化：dp[x][0] = 1, 代表把0划分位任意不超过x类都有一种分法0。最后返回 dp[m][n], 复杂度 O(mn)。

3.2. 多重组合数

给n类物品，每类物品有A[ i ]个，从这n类物品中取m个，有多少种取法，注意相同类别的物品无法区分。

这题看上去感觉和多重部分和问题很像，区别在于多重部分和要求取出的数总和为目标值，而这里是问具体的取法。我们用dp[ i ][j]来表示前i个物品取j个的取法。显然 dp[ i ][j] = sum(dp[ i ][j-k]) for k <= j and k <= A[i-1], 表示我们可以现在前i类(0->i-1)数里取j-k个，然后再在第i-1类数里取k个, 因此要求k必须小于第i个数的总个数。写个三重循环可以解决。

下面就开始骚操作了。我们分两种情况考虑。

if j <= A[i-1]: dp[ i ][j] = sum(dp[ i ][j-k-1]) + dp[ i ][j] for k=1->j-1
if j > A[i-1]: dp[ i ][j] = sum(dp[ i ][j-k-1]) + dp[ i ][j] - dp[ i ][j-1-A[i-1]] for k=1->j-1

同时注意 dp[ i ][j-1] = sum(dp[ i ][j-k-1]) for k=1->j-1, 因此综合起来的dp转移表达式就是：

if j <= A[i-1]: dp[ i ][j] = dp[ i ][j-1] + dp[ i ][j] for k=1->j-1
if j > A[i-1]: dp[ i ][j] = dp[ i ][j-1] + dp[ i ][j] - dp[ i ][j-1-A[i-1]] for k=1->j-1

这样就可以在 O(nm) 时间内解决了。。

初始化: 前x类物品取0个都有一种取法，因此dp[x][0] = 1, 其他项为0。返回 dp[n][m] 。

POJ 1065: Cow Bowling

给一个三角形矩阵，求顶层到底层的最小路径和，从位置(i, j)可以到达(i+1, j), (i+1, j+1)

思路：dp入门题。。

POJ 2229: Sumsets

找一些2^x(0<=x)，使它们的和为N。比如，N=7，结果为6

思路：最开始我想也不想就先构建可选的数的list, 然后再开始套背包模板，这样复杂度是O(NlogN)。但是后来发现有O(N)的解法。想了很久终于想出来了。dp[ i ] 设和为i的组合个数，如果i是奇数，那么只能通过dp[i-1]中的每个解+1得到dp[ i ]。如果i是偶数，则除此之外还可以通过dp[i//2]的解每个元素翻倍得到新的组合。可以证明不可能存在其他的情况了。这样复杂度是O(N).

POJ 2385: Apple catching

A, B两棵树交替每分钟掉下一个苹果，奶牛可以在树下面接苹果，但是同一时间只能站在一颗树下，问T分钟内最多移动W次能吃到的最多苹果个数。

思路：dp[ i ][k]来表示前i分钟移动k次能接到的最大苹果个数。dp[ i ][k] = catched + max(dp[i-1][k-1], dp[i-1][k]), catched 表示移动k次后能否接住苹果。

POJ 3616：Milking Time

农夫只能在M个时间段内给奶牛挤奶。给出每个时间段的开始时间，结束时间，和产奶量(v)，奶牛每次挤完牛奶必须休息一段时间。问最多能挤多少奶。

思路：这题的关键在于为了保证我们尽可能多的取不相交的时间段，我们应该按照结束时间排序（而不是开始时间）。这样可以保证一旦时间段i和之前的某时间段j不冲突，那么任意时间段k for k < j 一定不和i冲突，如果按照开始时间排序则不能保证这一点。搞清楚这一点后就简单了，dp[ i ] 为第i个时间段所能获得的最大奶量，则 dp[ i ] = max(dp[i-1], v[ i ] + dp[j]) 其中j是第一个不第i个时间段冲突的时间段。返回 dp[M-1]

POJ 3280: Cheapest Palindrome

给定一个字符串，可以任意位置添加或者减少字符，但是都有相应代价。问怎么用最小代价将该字符串变成回文的。

思路：一看这题就懵逼了。如果是只能减少字符那还好做，但是增加怎么办？后来仔细想一想发现一样做。dp[ i ][j] 来表示s[i:j+1]变成回文的最小代价。如果s[ i ] = s[j] 则 dp[ i ][j] = dp[i+1][j-1], 否则可以：

(1) 在s右边增加s[ i ], 代价 dp[i+1][j] + price_add[s[ i ]]
(2) 删除s[ i ], 代价 dp[i+1][j] + price_del[s[ i ]]
(3) 在s左边增加s[j], 代价 dp[ i ][j-1] + price_add[s[j]]
(4) 删除s[j], 代价 dp[ i ][j-1] + price_del[s[j]]

选择最小代价即可。

charleszhou 发表于 2019-2-21 00:29
POJ 1065: Cow Bowling

给一个三角形矩阵，求顶层到底层的最小路径和，从位置(i, j)可以到达(i+1, j),  ...

请教一下懂行的朋友。。为何我每次发出来都会出现格式错乱的情况。。。这么多玄幻的斜杠是怎么回事。。我都是在记事本里写好复制粘贴过来的。。

charleszhou 发表于 2019-2-21 01:00
请教一下懂行的朋友。。为何我每次发出来都会出现格式错乱的情况。。。这么多玄幻的斜杠是怎么回事。。我 ...

测试一下
[ i ]
[ i]
[i ]

看了看你上面的帖子，我觉得这个常用的【i】可能是导致困扰的原因。被解释成斜体了。

14417335 发表于 2019-2-21 01:26
测试一下
[ i ]
[ i]

谢谢版主！
测试测试
[i] 哈哈
[i, j] 哈哈
[ i ] 哈哈