用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;
};

 - 不和别人乘，就 `nums[i]`自己
 - `num[i]` 是负数，希望乘上前面的最大积
 - `num[i]` 是正数，希望乘上前面的最小积

 - **dp[i] [0]=min(dp[i−1] [0]∗num[i] ,  dp[i−1] [1] ∗ num[i],  num[i])**
 - **dp[i] [1]=max(dp[i−1] [0]∗num[i] ,  dp[i−1] [1] ∗ num[i],  num[i])**

 - **prevMin = Math.min(prevMin * num[i], prevMax * num[i], nums[i])**
 - **prevMax = Math.max(prevMin * num[i], prevMax * num[i], nums[i])**

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 coinChange = function (coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity);//初始化dp数组
    dp[0] = 0;//面额0只需要0个硬币兑换

    for (let i = 1; i <= amount; i++) {//循环面额
        for (let coin of coins) {//循环硬币数组
            if (i - coin >= 0) {//当面额大于硬币价值时
                //dp[i - coin]： 当前面额i减当前硬币价值所需要的最少硬币
                //dp[i] 可由 dp[i - coin] + 1 转换而来
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];//如果dp[amount] === Infinity，则无法兑换
};

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 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];
};

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 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];
};

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];
};

function testWeightBagProblem(wight, value, size) {
    const len = wight.length,
        dp = Array.from({ length: len + 1 }).map(//初始化dp数组
            () => Array(size + 1).fill(0)
        );
    //注意我们让i从1开始，因为我们有时会用到i - 1，为了防止数组越界
    //所以dp数组在初始化的时候，长度是wight.length+1
    for (let i = 1; i <= len; i++) {
        for (let j = 0; j <= size; j++) {
            //因为weight的长度是wight.length+1，并且物品下标从1开始，所以这里i要减1
            if (wight[i - 1] <= j) {
                dp[i][j] = Math.max(
                    dp[i - 1][j],
                    value[i - 1] + dp[i - 1][j - wight[i - 1]]
                )
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[len][size];
}

function test() {
    console.log(testWeightBagProblem([1, 3, 4], [15, 20, 30], 4));
}

test();

function testWeightBagProblem2(wight, value, size) {
    const len = wight.length,
        dp = Array(size + 1).fill(0);
    for (let i = 1; i <= len; i++) {
        //从后向前计算，如果从前向后的话，最新的值会覆盖老的值，导致计算结果不正确
          //dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wight[i - 1]] + value[i - 1])
        for (let j = size; j >= wight[i - 1]; j--) {
            dp[j] = Math.max(dp[j], dp[j - wight[i - 1]] + value[i - 1] );
        }
    }
    return dp[size];
}

//可以看成是0-1背包问题，给一个可装载重量为 sum / 2 的背包和 N 个物品，
//每个物品的重量记录在 nums 数组中，问是否在一种装法，能够恰好将背包装满？
var canPartition = function (nums) {
    let sum = 0
    let n = nums.length
    for (let i = 0; i < n; i++) {
        sum += nums[i]
    }
    if (sum % 2 !== 0) {//如果是奇数，那么分割不了，直接返回false
        return false
    }
    sum = sum / 2
    //dp[i][j]表示前i个物品是否能装满容积为j的背包，当dp[i][j]为true时表示恰好可以装满
    //最后求的是 dp[n][sum] 表示前n个物品能否把容量为sum的背包恰好装满
    //dp数组长度是n+1，而且是二维数组，第一维表示物品的索引，第二个维度表示背包大小
    let dp = new Array(n + 1).fill(0).map(() => new Array(sum + 1).fill(false))
    //dp数组初始化，dp[..][0] = true表示背包容量为0，这时候就已经装满了，
    //dp[0][..] = false 表示没有物品，肯定装不满
    for (let i = 0; i <= n; i++) {
        dp[i][0] = true
    }
    for (let i = 1; i <= n; i++) {//i从1开始遍历防止取dp[i - 1][j]的时候数组越界
        let num = nums[i - 1]
        //j从1开始，j为0的情况已经在dp数组初始化的时候完成了
        for (let j = 1; j <= sum; j++) {
            if (j - num < 0) {//背包容量不足 不能放入背包
                dp[i][j] = dp[i - 1][j];//dp[i][j]取决于前i-1个物品是否能前好装满j的容量
            } else {
                //dp[i - 1][j]表示不装入第i个物品
                //dp[i - 1][j-num]表示装入第i个，此时需要向前看前i - 1是否能装满j-num
                //和背包的区别，这里只是返回true和false 表示能否装满，不用计算价值
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
            }
        }
    }
    return dp[n][sum]
};

//状态转移方程 F[i, target] = F[i - 1, target] || F[i - 1, target - nums[i]]
//第 n 行的状态只依赖于第 n-1 行的状态
//状态压缩
var canPartition = function (nums) {
    let sum = nums.reduce((acc, num) => acc + num, 0);
    if (sum % 2) {
        return false;
    }
    sum = sum / 2;
    const dp = Array.from({ length: sum + 1 }).fill(false);
    dp[0] = true;

    for (let i = 1; i <= nums.length; i++) {
        //从后向前计算，如果从前向后的话，最新的值会覆盖老的值，导致计算结果不正确
        for (let j = sum; j > 0; j--) {
            dp[j] = dp[j] || (j - nums[i] >= 0 && dp[j - nums[i]]);
        }
    }

    return dp[sum];
};

//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串
};

//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;
};