如果元素不重复使用dfs,可重复使用dp(不过重不重复这两个都可以解决,只是好理解)
- 解
比如beautiful arrangement 4个元素
坑是pos 遍历1-4 把坑+1 坑从1开始增加 当坑(pos)>5 return;
先填pos = 1 ,used记录是否访问
1234之后,回溯
然后填pos = 2
然后3和4
NQUEEN问题也是不过是一行一行的填坑 - 代码固定
visited记录1
helper()
visited记录0 - 理解
pos是坑
开始给1填 填好1234
回溯
填坑 - 上一次和当前
helper(N, pos + 1, used);
为什么选的坑是pos。
分析
- pos = 3 结束?(pos = 3时 有 i = 3和4)
i = 3 时,pos = 3(回溯直接是回复状态 是回溯到i = 3的时候)
i = 4 , pos =3
pos = 2 结束?(i = 3和4)
i = 2 pos = 2 (回溯直接是回复状态)
i = 3 pos = 2
i = 4 pos = 2 - 如果不能符合,则每次if都过不去,然后i值一直迭代 直到回溯上个规模
- i = 1 时,会执行
used[1] = 1
help()
used[1] = 0 //重置状态
但是i = 2 的时候为什么不能把2填到pos = 1 中?
因为这时候的规模还在 i = 1 used[1] 被占了,
只有在i = 1 这轮循环结束之后才能把2放入pos = 1 中
也因为这样解才有这样的规律(先填pos = 1 的所有解遍历之后,遍历2 然后3 ) - pos = 3 上次是pos = 2
pos = 3 结束 ,回溯到pos = 2