用 javascript 分类刷 leetcode3. 动态规划 (图文视频讲解)

//暴力递归复杂度O(2^n)var fib = function (N) {    if (N == 0) return 0;    if (N == 1) return 1;    return fib(N - 1) + fib(N - 2);};

var fib = function (n) {    const memo = {}; // 对已算出的结果进行缓存
    const helper = (x) => {        if (memo[x]) return memo[x];        if (x == 0) return 0;        if (x == 1) return 1;        memo[x] = helper(x - 1) + helper(x - 2);        return memo[x];    };
    return helper(n);};

const fib = (n) => {    if (n <= 1) return n;    const dp = [0, 1];    for (let i = 2; i <= n; i++) {        //自底向上计算每个状态        dp[i] = dp[i - 1] + dp[i - 2];    }    return dp[n];};

const fib = (n) => {    if (n <= 1) return n;    //滚动数组 dp[i]只和dp[i-1]、dp[i-2]相关，只维护长度为2的滚动数组，不断替换数组元素    const dp = [0, 1];    let sum = null;    for (let i = 2; i <= n; i++) {        sum = dp[0] + dp[1];        dp[0] = dp[1];        dp[1] = sum;    }    return sum;};

var fib = function (N) {    if (N <= 1) {        return N;    }    let prev2 = 0;    let prev1 = 1;    let result = 0;    for (let i = 2; i <= N; i++) {        result = prev1 + prev2; //直接用两个变量就行        prev2 = prev1;        prev1 = result;    }    return result;};

var fib = function (N) {    if (N <= 1) {        return N;    }    let prev2 = 0;    let prev1 = 1;    let result = 0;    for (let i = 2; i <= N; i++) {        result = prev1 + prev2;        prev2 = prev1;        prev1 = result;    }    return result;};

var maxProduct = (nums) => {    let res = nums[0]    let prevMin = nums[0]    let prevMax = nums[0]    let temp1 = 0, temp2 = 0    for (let i = 1; i < nums.length; i++) {        temp1 = prevMin * nums[i]        temp2 = prevMax * nums[i]        prevMin = Math.min(temp1, temp2, nums[i])        prevMax = Math.max(temp1, temp2, nums[i])        res = Math.max(prevMax, res)    }    return res}

var uniquePaths = function (m, n) {    const f = new Array(m).fill(0).map(() => new Array(n).fill(0)); //初始dp数组    for (let i = 0; i < m; i++) {        //初始化列        f[i][0] = 1;    }    for (let j = 0; j < n; j++) {        //初始化行        f[0][j] = 1;    }    for (let i = 1; i < m; i++) {        for (let j = 1; j < n; j++) {            f[i][j] = f[i - 1][j] + f[i][j - 1];        }    }    return f[m - 1][n - 1];};
//状态压缩var uniquePaths = function (m, n) {    let cur = new Array(n).fill(1);    for (let i = 1; i < m; i++) {        for (let r = 1; r < n; r++) {            cur[r] = cur[r - 1] + cur[r];        }    }    return cur[n - 1];};

var integerBreak = function (n) {    //dp[i]为正整数i拆分之后的最大乘积    let dp = new Array(n + 1).fill(0);    dp[2] = 1;
    for (let i = 3; i <= n; i++) {        for (let j = 1; j < i; j++) {            //j*(i-j)表示把i拆分为j和i-j两个数相乘            //j*dp[i-j]表示把i拆分成j和继续把(i-j)这个数拆分，取(i-j)拆分结果中的最大乘积与j相乘            dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j);        }    }    return dp[n];};

//dp[i][j]表示s的前i个字符能否和p的前j个字符匹配const isMatch = (s, p) => {    if (s == null || p == null) return false;//极端情况 s和p都是空 返回false
    const sLen = s.length, pLen = p.length;
    const dp = new Array(sLen + 1);//因为位置是从0开始的，第0个位置是空字符串 所以初始化长度是sLen + 1    for (let i = 0; i < dp.length; i++) {//初始化dp数组        dp[i] = new Array(pLen + 1).fill(false); // 将项默认为false    }    // base case s和p第0个位置是匹配的    dp[0][0] = true;    for (let j = 1; j < pLen + 1; j++) {//初始化dp的第一列，此时s的位置是0        //情况1:如果p的第j-1个位置是*，则j的状态等于j-2的状态        //例如：s='' p='a*' 相当于p向前看2个位置如果匹配，则*相当于重复0个字符        if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2];    }    // 迭代    for (let i = 1; i < sLen + 1; i++) {        for (let j = 1; j < pLen + 1; j++) {
            //情况2:如果s和p当前字符是相等的 或者p当前位置是. 则当前的dp[i][j] 可由dp[i - 1][j - 1]转移过来            //当前位置相匹配，则s和p都向前看一位 如果前面所有字符相匹配 则当前位置前面的所有字符也匹配            //例如：s='XXXa' p='XXX.' 或者 s='XXXa' p='XXXa'            if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {                dp[i][j] = dp[i - 1][j - 1];            } else if (p[j - 1] == "*") {//情况3:进入当前字符不匹配的分支 如果当前p是* 则有可能会匹配                //s当前位置和p前一个位置相同 或者p前一个位置等于. 则有三种可能                //其中一种情况能匹配 则当前位置的状态也能匹配                //dp[i][j - 2]：p向前看2个位置，相当于*重复了0次，                //dp[i][j - 1]：p向前看1个位置，相当于*重复了1次                //dp[i - 1][j]：s向前看一个位置，相当于*重复了n次                //例如 s='XXXa' p='XXXa*'                if (s[i - 1] == p[j - 2] || p[j - 2] == ".") {                    dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];                } else {                    //情况4:s当前位置和p前2个位置不匹配，则相当于*重复了0次                    //例如 s='XXXb' p='XXXa*' 当前位置的状态和p向前看2个位置的状态相同                    dp[i][j] = dp[i][j - 2];                }            }        }    }    return dp[sLen][pLen]; // 长为sLen的s串 是否匹配 长为pLen的p串};

var uniquePathsWithObstacles = function (obstacleGrid) {    const m = obstacleGrid.length;    const n = obstacleGrid[0].length;    const dp = Array(m)        .fill()        .map((item) => Array(n).fill(0)); //初始dp数组
    for (let i = 0; i < m && obstacleGrid[i][0] === 0; ++i) {        //初始列        dp[i][0] = 1;    }
    for (let i = 0; i < n && obstacleGrid[0][i] === 0; ++i) {        //初始行        dp[0][i] = 1;    }
    for (let i = 1; i < m; ++i) {        for (let j = 1; j < n; ++j) {            //遇到障碍直接返回0            dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];        }    }
    return dp[m - 1][n - 1];};
//状态压缩var uniquePathsWithObstacles = function (obstacleGrid) {    let m = obstacleGrid.length;    let n = obstacleGrid[0].length;    let dp = Array(n).fill(0); //用0填充，因为现在有障碍物，当前dp数组元素的值还和obstacleGrid[i][j]有关    dp[0] = 1; //第一列 暂时用1填充    for (let i = 0; i < m; i++) {        for (let j = 0; j < n; j++) {            if (obstacleGrid[i][j] == 1) {                //注意条件，遇到障碍物dp[j]就变成0，这里包含了第一列的情况                dp[j] = 0;            } else if (j > 0) {                //只有当j>0 不是第一列了才能取到j - 1                dp[j] += dp[j - 1];            }        }    }    return dp[n - 1];};

const minDistance = (word1, word2) => {    let dp = Array.from(Array(word1.length + 1), () => Array(word2.length + 1).fill(0));
    //初始化数组，word1前i个字符最少需要i次操作，比如i次删除变成word2    for (let i = 1; i <= word1.length; i++) {        dp[i][0] = i;    }
    //初始化数组，word2前i个字符最少需要i次操作，比如j次插入变成word1    for (let j = 1; j <= word2.length; j++) {        dp[0][j] = j;    }
    for (let i = 1; i <= word1.length; i++) {        //循环word1和word2        for (let j = 1; j <= word2.length; j++) {            if (word1[i - 1] === word2[j - 1]) {                //如果word1[i-1] === word2[j-1],说明最后一个字符不用操作。                dp[i][j] = dp[i - 1][j - 1];            } else {                //dp[i-1][j] + 1：对应删除                //dp[i][j-1] + 1：对应新增                // dp[i-1][j-1] + 1：对应替换操作                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);            }        }    }
    return dp[word1.length][word2.length];};

var climbStairs = function (n) {    const memo = [];    memo[1] = 1;    memo[2] = 2;    for (let i = 3; i <= n; i++) {        memo[i] = memo[i - 2] + memo[i - 1];//所以到第n阶台阶可以从第n-2或n-1上来    }    return memo[n];};
//状态压缩var climbStairs = (n) => {    let prev = 1;    let cur = 1;    for (let i = 2; i < n + 1; i++) {        [prev, cur] = [cur, prev + cur]        // const temp = cur;   // 暂存上一次的cur        // cur = prev + cur;   // 当前的cur = 上上次cur + 上一次cur        // prev = temp;        // prev 更新为 上一次的cur    }    return cur;}

var numSquares = function (n) {    const dp = [...Array(n)].map((_) => 0); //初始化dp数组 当n为0的时候    for (let i = 1; i <= n; i++) {        dp[i] = i; // 最坏的情况就是每次+1 比如: dp[3]=1+1+1        for (let j = 1; i - j * j >= 0; j++) {//枚举前一个状态            dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程        }    }    return dp[n];};

//dp[i]表示0-i能偷的最大金额const rob = (nums) => {    const len = nums.length;    const dp = [nums[0], Math.max(nums[0], nums[1])]; //初始化dp数组的前两项    for (let i = 2; i < len; i++) {        //从第三个位置开始遍历        //dp[i - 2] + nums[i] 表示偷当前位置，那么i-1的位置不能偷，          //而且需要加上dp[i-2],也就是前i-2个房间的金钱        //dp[i - 1]表示偷当前位置，只偷i-1的房间        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);    }    return dp[len - 1]; //返回最后最大的项};
//状态压缩var rob = function (nums) {    if(nums.length === 1) return nums[0]    let len = nums.length;    let dp_0 = nums[0],        dp_1 = Math.max(nums[0], nums[1]);    let dp_max = dp_1;    for (let i = 2; i < len; i++) {        dp_max = Math.max(            dp_1, //不抢当前家            dp_0 + nums[i] //抢当前家        );        dp_0 = dp_1; //滚动交换变量        dp_1 = dp_max;    }    return dp_max;};