leetcode 第 388 场算法比赛

零、背景

今天比赛最后一题是动态规划不难，以前我都是写递归，这次写递推，被坑了，比赛期间没通过，以后还是要老老实实写递归。

A: 排序，从大到小判断
B: 排序，从大到小判断。
C: 枚举题，枚举并统计所有子串，然后枚举求答案。
D: 动态规划，推动出状态转移方程即可。

比赛排名：299
比赛代码：https://github.com/tiankonguse/leetcode-solutions/tree/master/contest

一、重新分装苹果

题意：给N堆苹果和M个箱子，问选择多少个箱子可以把所有苹果都装起来。

思路：苹果可以拆分，所以选择体积最大的若干个箱子即可。

对苹果求和，对箱子排序，从大到小选择箱子累计求和。

二、幸福值最大化的选择方案

题意：给N堆好苹果和K次选择，每次可以选择一堆苹果，选择后剩余的所有堆苹果都会坏掉一个。
问如何选择才能选最多的好苹果。

思路：不断如何选择，第 i 次选择的苹果在之前都会坏掉 i-1 个。
想要选择的好苹果最多，就要选择苹果最多的 k 堆苹果。

对苹果排序，从大到小选择，减去每次选择时坏掉的苹果即可。

三、数组中的最短非公共子字符串

题意：给一个字符串数组，求一个字符串的最长子串，当前子串不是其他任何字符串的子串。

思路：数据量不大，统计所有字符串的所有子串集合，枚举当前字符串的子串是否是答案。

对于一个子串，如果统计字符串里只出现一次，则说明其他字符串没出现。

四、 K 个不相交子数组的最大能量值

题意：给一个数组，求选择 k 个不想交的子数组，求最大积分。

子数组和: 第 i 个子数组的和定义为 sum[i]
积分公式：(-1)^(i+1) * sum[i] * (x - i + 1)

思路：定义状态f(n,k) ，含义为第 n 个位置之后的数组选择 k 个子数组的最优答案。

写出状态转移方程，分为两种情况。

1）不选择当前元素，则状态为 f(n+1, k)。
2）选择当前元素，则可能选择的长度最少是1，最长不能让 k 不够选。
复杂度：O(n*k*k)

优化：分析第二种情况，当前元素必须选择，提取出来，则刚好等价于f(n+1,k)必须选择第一个元素的情况。

所以定义新的状态F(n,k)代表当前元素必须选择的答案。

F(n,k)的状态转移方程通用分为两种情况。

1）只选择一个元素，即F(n,k)=V+f(n+1,k-1)
2）选择多个元素，依旧有很多选择。
提起第一个元素，发现等价于必须选择第一个元素。
故为F(n,k)=V+F(n+1,k)。

两个状态转移方程结合起来，就可以写为

f(n,k) = max(f(n+1,k), F(n,k))
F(n,k) = max(V+f(n+1,k-1), V+F(n+1,k))

当然，这道题在计算当前元素的值时，存在符号问题。
所以状态需要增加一个维度，来标记当前的符号。

新的状态为 f(s, n, k) 和 F(s, n, k)。

s 为 0 时代表负号，为 1 时为正号，V的值就为 s * nums[n] * k。

状态转移方程中，只有当前子数组选择完之后，符号才需要反转。
故新的状态转移方程为

f(s,n,k) = max(f(s,n+1,k), F(s,n,k))
F(s,n,k) = max(V+f(1-s,n+1,k-1), V+F(s,n+1,k))

状态方程我写出来后，还没有到 11 点，一看榜单，竟然一个人也没通过最后一题。

在敲代码时，我在由于是使用递推还是递归。

由于状态定义已经在函数里定义好了，我就去写递推了。
然后就面临一个抉择：如何初始化状态数组。

我一开始想的是偷懒一下，直接通过初始化来处理边界情况，就这样样例始终无法通过。
赛后我赶紧用递归重写，5分钟就写完了递归代码。

通过递推，很容易发现存在三个边界。

1）最后一个元素，只能选择一个子数组。
2）多个元素，只能选择一个子数组。
3）多个元素，每个都是一个子数组。
4）多个元素，任意选择。

五、最后

这次比赛自己偷懒没去处理边界情况，结果就被边界问题卡主了。 以后打比赛还是老老实实写递归吧，这样代码简单清晰，还好写。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code