问一道 DP 的题，

[jedihy]

L 代表 late ， A 代表 absence ， O 代表正常出席， input 是一个 string ，包含 L ， A ， O ，要求不能连续 3 次 late ，不能超过 1 次 absence ，就可以 reward 这个学生。

输出长度为 n 的 rewardable 的出席 string 的数量。实际上就是求 rewardable 的方案总数。哪位大神能写出这个 DP 来？

举个例子， n = 3
那么符合条件的方案有下面这些，只管方案数量，所以是 19 个。

['LLA', 'LLO', 'LAL', 'LAO', 'LOL', 'LOA', 'LOO', 'ALL', 'ALO', 'AOL', 'AOO', 'OLL', 'OLA', 'OLO', 'OAL', 'OAO', 'OOL', 'OOA', 'OOO']

[akking]

http://www.1point3acres.com/bbs/thread-228248-1-1.html
中间的的 code 感觉应该是对的。 不过可以把 3 维数组变成 2 维， 因为 f[i][j][k] only depends on f[i - 1][j][k].
我觉得这种 DP 不是一下子想出来的， 你先写个 DFS + backtracking 。会发现每层递归都会数 "A" 和 "L"的个数，自然就会想到是不是可以把这个信息保存下来用空间换时间。
至于能不能想到 3 维数组的关系...反正我是没想出来...

[binux]

我怎么觉得这个 A 一点作用没有，只要 string 不包含连续 3 个 L ，然后再随机替换一个 O 就可以了。
比如 n = 3 ，不包含 A 的有 ["LLO", "LOL", "LOO", "OLL", "OLO", "OOL", "OOO"]，其中有 12 个 O ，依次替换， 7+12 = 19
所以我预测 n = 4 有： 7 （填 O ）+ 6 （填 L ）+ (12+7)（ O 替换 A ）= 32 种

不知道对不对

[binux]

n = 4 有： 7 （填 O ）+ 6 （填 L ）+ 12 （原来的 O ）+7 （填 O 新增的 O ）+ (12-1)（ 填 L 里面的 O ）= 43 种

[binux]

pass, 下一题

[casparchen]

https://gist.github.com/anonymous/e16e84a3cb14663d0bf4a71afdfa938e

[casparchen]

下一题

[casparchen]

上面三种状态分别表示
M[i][0] 长度为 i 的以 L 结尾的合法字符串数量
M[i][1] 长度为 i 的以 A 结尾的合法字符串数量
M[i][2] 长度为 i 的以 O 结尾的合法字符串数量

[jedihy]

@binux @casparchen 卧操，厉害啊。就这么给秒了，我写了好半天都是个错的。都是 OIer 吗？

[jedihy]

@akking 我是写的 DFS ，一开始把这个 DP 想太复杂了，发现写不出。

[jedihy]

@akking 地里面那个帖子的代码是错的，和我 DFS 的结果不一样，但是楼上两位的结果是对的，有些惊艳。

[jedihy]

@binux 写成状态转移方程才算对 ^_^

[jedihy]

@casparchen 没有看太懂这个方程是怎么推出来的，能指点一下吗

[jedihy]

@casparchen
https://gist.github.com/csujedihy/4e8e21df2ea1fd29d651beabc815e0af
想了一下，加了点注释，您能看看是我这么理解的吗？

[nodekey]

挖个坟（手动滑稽
只能算个递推吧，思路和 2 楼一样
https://gist.github.com/KeyLD/331c81bac99122d2f3e4e236efee576c