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

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

  •  
  •   Vegetables · 2018-11-27 22:53:19 +08:00 · 3233 次点击
    这是一个创建于 1948 天前的主题,其中的信息可能已经有所发展或是发生改变。
    9 条回复    2019-03-10 09:50:12 +08:00
    casparchen
        1
    casparchen  
       2018-11-27 23:08:27 +08:00
    是要问有多少种方案,还是问随便一种?
    Vegetables
        2
    Vegetables  
    OP
       2018-11-27 23:15:34 +08:00
    @casparchen 所有符合要求的结果
    casparchen
        3
    casparchen  
       2018-11-27 23:18:06 +08:00
    如果要列出所有结果那一个 DFS 不就行了
    casparchen
        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]
    ```
    EchoUtopia
        5
    EchoUtopia  
       2018-11-27 23:25:50 +08:00 via Android   ❤️ 1
    选 n 的时候:n,f(n-2);不选 n 的时候:f(n-1)
    rabbbit
        6
    rabbbit  
       2018-11-28 00:12:36 +08:00   ❤️ 1
    Wincer
        7
    Wincer  
       2018-11-28 00:13:39 +08:00 via Android
    @rabbbit 什么主题
    azygote
        8
    azygote  
       2018-11-28 01:41:24 +08:00 via iPhone
    回溯法
    GenialX2
        9
    GenialX2  
       2019-03-10 09:50:12 +08:00   ❤️ 1
    这道题目也许和青蛙跳的问题类似,希望这篇文章对你有所帮助:[一只青蛙跳出来的分治法、回溯法与动态规划]( https://www.cnblogs.com/genialx/p/10191366.html)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   960 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 21:53 · PVG 05:53 · LAX 14:53 · JFK 17:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.