V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
jedihy
V2EX  ›  算法

问一道 DP 的题,

  •  
  •   jedihy · 2017-02-23 05:50:11 +08:00 · 4327 次点击
    这是一个创建于 2829 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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']
    14 条回复    2017-05-19 20:57:08 +08:00
    akking
        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 维数组的关系...反正我是没想出来...
    binux
        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 种

    不知道对不对
    binux
        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 种
    binux
        4
    binux  
       2017-02-23 07:18:07 +08:00
    pass, 下一题
    casparchen
        5
    casparchen  
       2017-02-23 07:37:05 +08:00   ❤️ 1
    casparchen
        6
    casparchen  
       2017-02-23 07:54:12 +08:00
    下一题
    casparchen
        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 结尾的合法字符串数量
    jedihy
        8
    jedihy  
    OP
       2017-02-23 08:44:24 +08:00
    @binux @casparchen 卧操,厉害啊。就这么给秒了,我写了好半天都是个错的。都是 OIer 吗?
    jedihy
        9
    jedihy  
    OP
       2017-02-23 08:46:19 +08:00
    @akking 我是写的 DFS ,一开始把这个 DP 想太复杂了,发现写不出。
    jedihy
        10
    jedihy  
    OP
       2017-02-23 08:48:06 +08:00
    @akking 地里面那个帖子的代码是错的,和我 DFS 的结果不一样,但是楼上两位的结果是对的,有些惊艳。
    jedihy
        11
    jedihy  
    OP
       2017-02-23 08:54:54 +08:00
    @binux 写成状态转移方程才算对 ^_^
    jedihy
        12
    jedihy  
    OP
       2017-02-23 12:08:03 +08:00
    @casparchen 没有看太懂这个方程是怎么推出来的,能指点一下吗
    jedihy
        13
    jedihy  
    OP
       2017-02-23 14:32:02 +08:00
    @casparchen
    https://gist.github.com/csujedihy/4e8e21df2ea1fd29d651beabc815e0af
    想了一下,加了点注释,您能看看是我这么理解的吗?
    nodekey
        14
    nodekey  
       2017-05-19 20:57:08 +08:00
    挖个坟(手动滑稽
    只能算个递推吧,思路和 2 楼一样
    https://gist.github.com/KeyLD/331c81bac99122d2f3e4e236efee576c
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1010 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 22:02 · PVG 06:02 · LAX 14:02 · JFK 17:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.