这是一个创建于 2860 天前的主题，其中的信息可能已经有所发展或是发生改变。
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