4.27

53. 最大子序和

问题是怎么保证当前k最大就替换

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    // 动态规划
    var res = nums[0];
    var pre = 0;
    for(let k of nums) {
        pre = Math.max(k, pre + k)
        res = Math.max(res, pre)
    };
    return res
};

70. 爬楼梯

/**
 * @param {number} n
 * @return {number}
 */
// 递归为啥报错了
var climbStairs = function(n) {
    // 动态规划
    // f(n) = f(n - 2) + f(n - 1)
    if (n <= 2) {
        return n;
    }
    return climbStairs(n - 1) + climbStairs( n - 2);
};
// 求动态规划
dp[i] = dp[i - 2] + dp[i - 1]
var climbStairs = function(n) {
    let p = 0, q = 0, r = 1;
    for (let i = 1; i <= n; ++i) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
};

46. 全排列

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let len = nums.length, result = [], visited = new Array(len).fill(false);
    const dfs = (depth, path, visited) => {
        // 遍历到叶子结点了，可以返回了
        if(depth === len) {
            result.push([...path]);
        }
        for(let i = 0; i < len; i++) {
            // 如果没遍历过
            if(!visited[i]) {
                // 压入 path 数组，然后是否遍历过的数组此下标处变为 true
                path.push(nums[i]);
                visited[i] = true;
                // 继续 dfs，直到最后一层
                dfs(depth + 1, path, visited);
                // 进行回溯，还原，以便下一次使用
                visited[i] = false;
                path.pop();
            }
        }
    }
    dfs(0, [], visited);
    return result;
}