请问如何将记忆化搜索解法转成动态规划写法
来源：1-5 大厂面试为什么总考算法？
Potter520
2023-06-30
比如这个题目：2741. 特别的排列
这其实就是全排列问题，画图我能看到重叠子问题，然后利用记忆化搜索，写出如下算法。
/**
* 记忆化搜索
* @param {*} nums
*/
var specialPerm = function (nums) {
let n = nums.length;
let visited = Array(n).fill(false);
let meno = Array(n)
.fill(-1)
.map(() => Array((1 << n) - 1).fill(-1));
let MOD = 1e9 + 7;
//! 从深度0至depth，获得的特殊排序个数。prevPos：前一个元素索引, mask: 表示已选择的数的索引二进制值
function dfs(depth, prevPos, mask) {
if (depth == n) {
return 1;
}
//! 已选择的数
if (meno[prevPos][mask] !== -1) {
return meno[prevPos][mask];
}
let res = 0;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
//! mask=0 表示没有选择任何元素，也就是第一个开始元素，所以直接递归下去
if (mask == 0) {
visited[i] = true;
res += dfs(depth + 1, i, mask | (1 << i));
visited[i] = false;
} else if (nums[i] % nums[prevPos] == 0 || nums[prevPos] % nums[i] == 0) {
visited[i] = true;
res += dfs(depth + 1, i, mask | (1 << i));
visited[i] = false;
}
res %= MOD;
}
}
meno[prevPos][mask] = res;
return res;
}
return dfs(0, 0, 0);
};
提交可以通过，但是要改成动态规划写法，我想不清base case、dp的清楚定义、状态转移。我尝试画图了也没有搞清楚，疑问一：请问老师有什么方法能帮助我想清楚这些东西吗？也翻看了别人的dp解法，还是没有看懂。其实之前也有总结过不少动态规划的题目，但是要做这种转换还是想不清。对于我这种状态有什么建议呢？
疑问二：记忆化搜索算法转动态规划，有没有什么技巧。比如：什么对应什么，以及如何改，要遵循什么规则等等。
2回答
-
首先，在你的代码中，visited 这个数组是不必要的。因为 visited 的信息就在 mask 中。mask 的第 i 位是 0 表示这个元素没有被选过，是 1 表示选过，所以我先简单优化了一下你现在的代码，扔掉了 visited。注意原先对 if(!visited[i]) 的判断变成了
if ((mask & (1 << i)) == 0)
即 mask 的第 i 位是 0。
(其实，递归函数中的 deoth 参数也可以扔掉，因为 depth 的信息也在 mask 中，即 mask 中 1 的数量。但是因为我对 js 不熟，不确定是不是有更直接的方式获得一个数字的二进制表示中 1 的数量，且 depth 作为函数参数传递在我看来可以接受，就保留了。)
另外，我将 meno 的拼写修改成了 memo，memo 是备忘录的意思，也是记忆化搜索这种方式的英文 memoization 的前四个字母。不过我也习惯把这个数组叫 dp。
var specialPerm = function (nums) { let n = nums.length; let memo = Array(n) .fill(-1) .map(() => Array((1 << n) - 1).fill(-1)); let MOD = 1e9 + 7; //! 从深度0至depth，获得的特殊排序个数。prevPos：前一个元素索引, mask: 表示已选择的数的索引二进制值 function dfs(depth, prevPos, mask) { if (depth == n) { return 1; } //! 已选择的数 if (memo[prevPos][mask] !== -1) { return memo[prevPos][mask]; } //!!!!!!!!!! // 注意这段代码 let res = 0; for (let i = 0; i < n; i++) { if ((mask & (1 << i)) == 0) { //! mask=0 表示没有选择任何元素，也就是第一个开始元素，所以直接递归下去 if (mask == 0) { res += dfs(depth + 1, i, mask | (1 << i)); } else if (nums[i] % nums[prevPos] == 0 || nums[prevPos] % nums[i] == 0) { res += dfs(depth + 1, i, mask | (1 << i)); } res %= MOD; } } memo[prevPos][mask] = res; // !!!!!!!!!! return res; } return dfs(0, 0, 0); };==========
下面说你的问题。我先把你的这个代码写成 dp，然后再来回答一些"所谓"的“基本原则"（
var specialPerm = function (nums) { let n = nums.length; let memo = Array(n) .fill(-1) .map(() => Array((1 << n) - 1).fill(-1)); let MOD = 1e9 + 7; // A!!! // 对应上面递归算法的 // if (depth == n) return 1; // 也就是不管 prevPos 的值，只要 mask == (1 << n) - 1，结果都是 1 for(let prevPos = 0; prevPos < n; prevPos ++) memo[prevPos][(1 << n) - 1] = 1; // B!!! // 逆序遍历 mask for(let mask = (1 << n) - 2; mask >= 0; mask --){ // 遍历 prevPos for(let prevPos = 0; prevPos < n; prevPos ++){ // C!!! // 注意，下面这段代码，和上面我标识 // !!!!!!!!! 的代码完全相同 // 区别只要在上面是递归调用 dfs(i, mask | (1 << i)) 的地方 // 下面的代码直接调用 memo[i][mask | (1 << i)] let res = 0; for(let i = 0; i < n; i ++){ if ((mask & (1 << i)) == 0){ if (mask == 0) { res += memo[i][mask | (1 << i)]; } else if (nums[i] % nums[prevPos] == 0 || nums[prevPos] % nums[i] == 0) { res += memo[i][mask | (1 << i)]; } res %= MOD; } } memo[prevPos][mask] = res; // !!!!!!!!!! } } return memo[0][0]; };下面看一些基本原则：
1）
递归调用分两部分：递归到底的情况和递归过程。
递归到底的情况对应上面代码的 A!!!，这部分应该很好理解；
递归过程对应上面代码的 B!!! 和 C!!!
2）
记忆化搜索的递归过程，本质就是状态转移。所以，上面 C!!! 的代码逻辑是完全相同的。
3）
最重要的区别是，对于递归过程，我们不需要关心使用什么“顺序”去访问这些状态，但是在做 dp 的时候，我们需要关心这个状态的顺序。也就是上面 B!!! 代码做的事情（两重循环）
具体就是在这个例子里，我们逆序遍历 mask 是重要的，顺序遍历 mask 是不可以的。因为你可以看状态转移，我们为了计算 memo[prevPos][mask]，需要访问 memo[i][mask | (1 << i)] 的值，而 mask | (1 << i) 的值肯定比 mask 大。所以，我们为了计算更小的 mask 对应的状态，必须先计算完 更大的 mask 对应的状态。
（在这个例子里，对 prevPos 的遍历没有顺序要求，我是从小到大遍历，也可以从大到小遍历。）
4）
想清楚这三件事儿，任何记忆搜索的代码都可以修改成动态规划。再总结一遍，这三件事儿是：
基本状态是什么（对应递归的终止条件）
状态转移是什么（对应递归过程的逻辑）
按照什么顺序计算这些状态（在递归的时候基本不用考虑这件事儿）
因为 3 是做递归的时候不用考虑的，所以如果你真的理解记忆化搜索，面对一个可以 dp 的问题，写出记忆化搜索的代码，是比写出 dp 代码更容易的，这是非常正常的事情。 因为在一些情况下，这个状态的访问顺序可以很复杂，不一定是正序或者是逆序，有可能是一个状态图的拓扑序。使用递归其实是简化了这个过程，而非复杂化了这个过程。
5）
更神奇的是，在很多时候，记忆化搜索是比 dp 效率高的（比如我测试这个问题就是如此）。这是因为记忆化搜索只会计算为了计算出最终结果所需要的状态，有可能会省略一些状态的计算。而 dp 一定遍历了所有的状态。
当然，dp 也有更具有优势的时候。比如如果所有状态都需要计算的话，非递归的代码通常性能更好。更重要的是，dp 的方式提供了算法优化的空间，比如我在课程中介绍的滚动数组的方式。更进阶的情况包括把整个 dp 表组织成其他数据结构（比如线段树）以快速查询某些信息。但这些都属于很进阶的内容了，面试 200% 不会涉及。
6）
综上，如果你愿意，当然可以尝试把每一个记忆化搜索的代码改成 dp，但其实对于现代计算机来说，这并非必须，也不一定更优。
继续加油！：）
032023-07-26 -
甲骨文_0001
2023-07-26
var specialPerm = function(nums) { let resArr = [] // 先求出所有全排列 permute(nums, 0, [], resArr) let cnt = 0; // 符合条件的结果计数 for( let row = 0; row < resArr.length; row ++ ){ // 对第row行个子数组考察 let bSpecial = true; // 接着对每行按列来判断，如果有一个下标处不符合条件，直接break,同时设bSpecial=false; for( let i = 0; i < resArr[row].length - 1; i ++ ){ if( !(resArr[row][i] % resArr[row][i+1] == 0 || resArr[row][i+1] % resArr[row][i] == 0) ){ bSpecial = false break; } } // for i if(bSpecial){ // 如果某行每列都判断下来了，都符合条件，计数加1 cnt++; } } // for row return cnt; }; function permute( nums, mask, tmp, resArr ){ if( tmp.length >= nums.length ){ resArr.push([...tmp]) return; } for( let i = 0; i < nums.length; i ++ ){ // let ss = mask.toString(2) if( (mask & (1 << i)) == 0 ){ tmp.push(nums[i]) permute( nums, mask | (1 << i), tmp, resArr ) tmp.pop() } } // for i }老师，这道题目我自己的方法是首先求出全排列，然后按照
对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0
这个逻辑来对一个排列进行判断，因为上述同学的递归 dfs(depth, prevPos, mask) 我一下想不出来，需要消化，然后我的方法在我自己测试的时候，(如下截图)对同一组用例： [24,3,27,54,9,90,30,60,20,100]，在我的chrome上跑是4个计数，然后判题系统是抛错了，不晓得这个错是怎么回事。。。。。
012023-07-28
相似问题