美文网首页
dfs特征(元素不重复)

dfs特征(元素不重复)

作者: KeDaiBiaO1 | 来源:发表于2017-10-26 15:34 被阅读0次

    如果元素不重复使用dfs,可重复使用dp(不过重不重复这两个都可以解决,只是好理解)


    1. 比如beautiful arrangement 4个元素
      坑是pos 遍历1-4 把坑+1 坑从1开始增加 当坑(pos)>5 return;
      先填pos = 1 ,used记录是否访问
      1234之后,回溯
      然后填pos = 2
      然后3和4
      NQUEEN问题也是不过是一行一行的填坑
    2. 代码固定
      visited记录1
      helper()
      visited记录0
    3. 理解
      pos是坑
      开始给1填 填好1234
      回溯
      填坑
    4. 上一次和当前
      helper(N, pos + 1, used);
      为什么选的坑是pos。
    分析
    1. 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
    2. 如果不能符合,则每次if都过不去,然后i值一直迭代 直到回溯上个规模
    3. 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 )
    4. pos = 3 上次是pos = 2
      pos = 3 结束 ,回溯到pos = 2

    相关文章

      网友评论

          本文标题:dfs特征(元素不重复)

          本文链接:https://www.haomeiwen.com/subject/qqhkpxtx.html