Leetcode 1641 回溯分享

Question

老师，这次我不问问题，今天的每日一题我用的是纯粹递归回溯来求解的，作一个分享。动态规划太有技巧了，要找规律，我还是偏向于这种传统的求解方式 求解。 虽然不是高效的，但是通过了测试用例。

/**
 * @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

}

Answer 1

liuyubobobo 2023-04-04 04:20:48

如果暴力法（回溯就是暴力法）是可以 work 的，当然 ok。但是在回溯不能 work 的时候，就要思考优化的方式了。实际上，动态规划本身就是回溯的一种优化方向。一旦发现回溯的过程中存在重叠子问题，就可以做记忆化搜索，如果可以记忆化搜索，就可以动态规划。

整个这个思路也是我这个课程介绍动态规划的思路：回溯 -> 记忆化搜索 -> 动态规划。

当然，并不是所有的回溯的代码都能直接做记忆化搜索的。这是动态规划最 tricy 的地方：为了可以记忆化，很多时候需要“聪明地”设计搜索的状态（dfs 的参数是什么，背包就是很好的例子）。如果这个回溯到动态规划的算法思路理清楚了，学习动态规划的重点，其实就是去看不同类型的问题，是怎么设计状态的，去体会为什么在这个状态下，就可以做记忆化搜索了（满足了最优子结构和重叠子问题。）这个状态的设计可以无限难，其实本质就是搜索本身是异常灵活的一件事情。很多时候“换个方式做搜索”，会得到完全不同的性能效果。

（当然，动态规划还有一类技巧是基于已有的状态设计做优化，也就是加速状态转移的过程，就更进阶了。）

不管怎样，能熟练使用回溯都是基础。

随便聊两句，继续加油！：）

• 提问者 甲骨文_0001 #1

  谢谢老师😊