如何在 数组 [0, 1, 2, 3, ..., n] 中选取 m 个不相邻的整数？
Vegetables · 2018-11-27 22:53:19 +08:00 · 3472 次点击这是一个创建于 2216 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
1
casparchen 2018-11-27 23:08:27 +08:00
是要问有多少种方案，还是问随便一种？
|
 |
2
Vegetables OP @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
 |
 |
8
azygote 2018-11-28 01:41:24 +08:00 via iPhone
回溯法
|
 |
9
t9ouKal33vGEZyf5 2019-03-10 09:50:12 +08:00 1
这道题目也许和青蛙跳的问题类似，希望这篇文章对你有所帮助：[一只青蛙跳出来的分治法、回溯法与动态规划]( https://www.cnblogs.com/genialx/p/10191366.html)
|
Select Language