记忆化搜索中, memo 赋值语句 放置位置的疑问 ^_^

Question

老师，上图中写的就是我自己的理解，不知道对不对哈: ）

Answer 1

liuyubobobo 2021-10-19 04:10:45

关键问题是，你为什么这样修改逻辑？这样修改逻辑，你遵守的变量的语义是什么？现在，你的状态定义是怎样的？请解释你的逻辑。

• 提问者 甲骨文_0001 #1

  private int dfs(int visited, int v, int left){
  
      if(memo[visited][v] != -1) return memo[visited][v];
  
      visited += (1 << v); // 这里visited改变了，我想以visited改变后的值作为key，来检索
      left --;
      if(v == end && left == 0){
          memo[visited][v] = 1; // ************
          visited -= (1 << v);
          // memo[visited][v] = 1;
          return 1;
      }
  
      int x = v / C, y = v % C;
      int res = 0;
      for(int d = 0; d < 4; d ++){
          int nextx = x + dirs[d][0], nexty = y + dirs[d][1];
          int next = nextx * C + nexty;
          if(inArea(nextx, nexty) && grid[nextx][nexty] == 0 && (visited & (1 << next)) == 0)
              res += dfs(visited, next, left);
      }
  
      memo[visited][v] = res; // *********
      visited -= (1 << v);
     // memo[visited][v] = res;
      return res;
  }
  
  老师，我之所以会这么想，也是因为之前对记忆化搜索这段看了几遍，当时没消化，到现在，我自己有那么点理解了，才提出了自己的一个观点，老师你讲的我能听明白，只是我自己在做的过程中，会有上述提问的想法哈.....

• liuyubobobo 回复 提问者 甲骨文_0001 #2

  如果你以 visited 改变的值做 key，但 if(memo[visited][v] != -1) return memo[visited][v]; 这句话没有变。那么你存的状态和读的状态是不统一的。（存的改变后的状态，读的改变前的状态。）
  
  你这个思路是可以走通的，但这个代码貌似有问题。而且走通以后，外层的调用也需要改变。
  
  我向你真正提的问题是：在你的逻辑下，memo[visited][v] 是什么意思。我的逻辑中，memo[visited][v] 的意思是，当前已经走过了 visited 表示的节点，新来到了 v 节点，看能否形成哈密尔顿回路。这是我说的语义的意思。所有的逻辑，是围绕着这个定义展开的，而不是只是看语句之间的顺序是怎样的。语句之间之所以有这个顺序，是因为他表达了在这个语义下，我们需要的逻辑。

• 提问者 甲骨文_0001 回复 liuyubobobo #3

  谢谢老师🙏