Leetcode 1641 回溯分享
来源：1-5 大厂面试为什么总考算法？
甲骨文_0001
2023-03-29
老师，这次我不问问题，今天的每日一题我用的是纯粹递归回溯来求解的，作一个分享。动态规划太有技巧了，要找规律，我还是偏向于这种传统的求解方式 求解。 虽然不是高效的，但是通过了测试用例。
/**
* @param {number} n
* @return {number}
*/
const alphabets = ['a', 'e', 'i', 'o', 'u']; // 元音字符集
var countVowelStrings = function(n) {
// tmpArr: 临时用于存放元素的数组, resArr: 最终收集到的结果所组成的数组
let tmpArr = [], resArr = [];
dfs(alphabets, n, 0, tmpArr, resArr);
return resArr.length;
};
//arr: 考察的数组(元音字符集), N:期待长度为N, index: 从index个开始考察, tmpArr: 临时用于存放元素的数组, resArr: 最终收集到的结果所组成的数组
function dfs( arr, N, index, tmpArr, resArr ){
if( tmpArr.length == N ){ // tmpArr 到了指定长度 N
resArr.push([...tmpArr]); // 找着一个结果，通过拷贝tmpArr放入到resArr中
return;
}
for( let i = index; i < arr.length; i ++ ){
tmpArr.push( arr[i] ); // 进一个元素到tmpArr
dfs( arr, N, i, tmpArr, resArr ); // 从当前遍历到的i下标继续后续dfs调用
tmpArr.pop(); // 回溯
} // for i
}
写回答
1回答
-
liuyubobobo
2023-04-04
如果暴力法（回溯就是暴力法）是可以 work 的，当然 ok。但是在回溯不能 work 的时候，就要思考优化的方式了。实际上，动态规划本身就是回溯的一种优化方向。一旦发现回溯的过程中存在重叠子问题，就可以做记忆化搜索，如果可以记忆化搜索，就可以动态规划。
整个这个思路也是我这个课程介绍动态规划的思路：回溯 -> 记忆化搜索 -> 动态规划。
当然，并不是所有的回溯的代码都能直接做记忆化搜索的。这是动态规划最 tricy 的地方：为了可以记忆化，很多时候需要“聪明地”设计搜索的状态（dfs 的参数是什么，背包就是很好的例子）。如果这个回溯到动态规划的算法思路理清楚了，学习动态规划的重点，其实就是去看不同类型的问题，是怎么设计状态的，去体会为什么在这个状态下，就可以做记忆化搜索了（满足了最优子结构和重叠子问题。）这个状态的设计可以无限难，其实本质就是搜索本身是异常灵活的一件事情。很多时候“换个方式做搜索”，会得到完全不同的性能效果。
（当然，动态规划还有一类技巧是基于已有的状态设计做优化，也就是加速状态转移的过程，就更进阶了。）
不管怎样，能熟练使用回溯都是基础。
随便聊两句，继续加油！：）
112023-04-04
相似问题
LeetCode 62题回溯与动态规划
回答 1
leetcode 37问题
回答 3
递归与回溯有什么区别？怎么区分？
回答 1
Leetcode第279题使用回溯法超时
回答 1
分享一个本题的python解决思路
回答 2