这是一个创建于 3211 天前的主题，其中的信息可能已经有所发展或是发生改变。
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']
输出长度为 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']
14 条回复 2017-05-19 20:57:08 +08:00
 | 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 |
Select Language