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

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 maxCoins = function (nums) {    const n = nums.length;    let points = [1, ...nums, 1]; //两边添加虚拟气球    const dp = Array.from(Array(n + 2), () => Array(n + 2).fill(0)); //dp数组初始化    //自底向上转移状态    for (let i = n; i >= 0; i--) {        //i不断减小        for (let j = i + 1; j < n + 2; j++) {            //j不断扩大            for (let k = i + 1; k < j; k++) {                //枚举k在i和j中的所有可能                //i-j能获得的最大数量的金币等于 戳破当前的气球获得的金钱加上之前i-k,k-j区间中已经获得的金币                dp[i][j] = Math.max(                    //挑战最大值                    dp[i][j],                    dp[i][k] + dp[k][j] + points[j] * points[k] * points[i]                );            }        }    }    return dp[0][n + 1];};

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

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 minPathSum = function(dp) {    let row = dp.length, col = dp[0].length
    for(let i = 1; i < row; i++)//初始化第一列        dp[i][0] += dp[i - 1][0]
    for(let j = 1; j < col; j++)//初始化第一行        dp[0][j] += dp[0][j - 1]
    for(let i = 1; i < row; i++)        for(let j = 1; j < col; j++)            dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1])//取上面和左边最小的
    return dp[row - 1][col - 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];};

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，则无法兑换};

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