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

如何在 数组 [0, 1, 2, 3, ..., n] 中选取 m 个不相邻的整数?

  •  
  •   Vegetables · 2018-11-27 22:53:19 +08:00 · 1205 次点击
    这是一个创建于 379 天前的主题,其中的信息可能已经有所发展或是发生改变。
    9 回复  |  直到 2019-03-10 09:50:12 +08:00
        1
    casparchen   2018-11-27 23:08:27 +08:00
    是要问有多少种方案,还是问随便一种?
        2
    Vegetables   2018-11-27 23:15:34 +08:00
    @casparchen 所有符合要求的结果
        3
    casparchen   2018-11-27 23:18:06 +08:00
    如果要列出所有结果那一个 DFS 不就行了
        4
    casparchen   2018-11-27 23:25:16 +08:00   ♥ 1
    ```
    def dfs(lst, start, m):
    if m <= 0:
    print(list(filter(lambda x: x != None, lst)))
    else:
    for i in range(start, len(lst)):
    lst[i] = i
    dfs(lst, i+2, m-1)
    lst[i] = None
    dfs([None for i in range(9)], 0, 5)
    ```

    ```
    [0, 2, 4, 6, 8]
    [Finished in 0.1s]
    ```
        5
    EchoUtopia   2018-11-27 23:25:50 +08:00 via Android   ♥ 1
    选 n 的时候:n,f(n-2);不选 n 的时候:f(n-1)
        6
    rabbbit   2018-11-28 00:12:36 +08:00   ♥ 1
        7
    Wincer   2018-11-28 00:13:39 +08:00 via Android
    @rabbbit 什么主题
        8
    azygote   2018-11-28 01:41:24 +08:00 via iPhone
    回溯法
        9
    GenialX2   276 天前   ♥ 1
    这道题目也许和青蛙跳的问题类似,希望这篇文章对你有所帮助:[一只青蛙跳出来的分治法、回溯法与动态规划]( https://www.cnblogs.com/genialx/p/10191366.html)
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   979 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 24ms · UTC 21:54 · PVG 05:54 · LAX 13:54 · JFK 16:54
    ♥ Do have faith in what you're doing.