1
akking 2017-02-23 06:43:12 +08:00
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 维数组的关系...反正我是没想出来... |
2
binux 2017-02-23 06:57:50 +08:00
我怎么觉得这个 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 种 不知道对不对 |
3
binux 2017-02-23 07:10:57 +08:00 1
n = 4 有: 7 (填 O )+ 6 (填 L )+ 12 (原来的 O )+7 (填 O 新增的 O )+ (12-1)( 填 L 里面的 O )= 43 种
|
4
binux 2017-02-23 07:18:07 +08:00
pass, 下一题
|
5
casparchen 2017-02-23 07:37:05 +08:00 1
|
6
casparchen 2017-02-23 07:54:12 +08:00
下一题
|
7
casparchen 2017-02-23 08:05:49 +08:00 1
上面三种状态分别表示
M[i][0] 长度为 i 的以 L 结尾的合法字符串数量 M[i][1] 长度为 i 的以 A 结尾的合法字符串数量 M[i][2] 长度为 i 的以 O 结尾的合法字符串数量 |
8
jedihy OP @binux @casparchen 卧操,厉害啊。就这么给秒了,我写了好半天都是个错的。都是 OIer 吗?
|
12
jedihy OP @casparchen 没有看太懂这个方程是怎么推出来的,能指点一下吗
|
13
jedihy OP @casparchen
https://gist.github.com/csujedihy/4e8e21df2ea1fd29d651beabc815e0af 想了一下,加了点注释,您能看看是我这么理解的吗? |
14
nodekey 2017-05-19 20:57:08 +08:00
|