提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Javascript

当前栏目

js分类刷leetcode动态规划

2023-02-18 15:49:45 时间

什么是动态规划

动态规划，英文：Dynamic Programming，简称DP，将问题分解为互相重叠的子问题，通过反复求解子问题来解决原问题就是动态规划，如果某一问题有很多重叠子问题，使用动态规划来解是比较有效的。

求解动态规划的核心问题是穷举，但是这类问题穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。重叠子问题、最优子结构、状态转移方程就是动态规划三要素

动态规划和其他算法的区别

  1. 动态规划和分治的区别：动态规划和分治都有最优子结构 ，但是分治的子问题不重叠
  2. 动态规划和贪心的区别：动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优解，所以它永远是局部最优，但是全局的解不一定是最优的。
  3. 动态规划和递归的区别：递归和回溯可能存在非常多的重复计算，动态规划可以用递归加记忆化的方式减少不必要的重复计算

动态规划的解题方法

  • 递归+记忆化(自顶向下)
  • 动态规划（自底向上）
ds_135

解动态规划题目的步骤

  1. 根据重叠子问题定义状态
  2. 寻找最优子结构推导状态转移方程
  3. 确定dp初始状态
  4. 确定输出值

斐波那契的动态规划的解题思路

ds_3

动画过大，点击查看

暴力递归
//暴力递归复杂度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;
};

72. 编辑距离 （hard）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符 删除一个字符 替换一个字符示例 1：输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 示例 2：输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')提示：0 <= word1.length, word2.length <= 500 word1 和 word2 由小写英文字母组成

方法1.动态规划
ds_76
ds_77
  • 思路：dp[i][j] 表示word1前i个字符和word2前j个字符的最少编辑距离。
    1. 如果word1[i-1] === word2[j-1],说明最后一个字符不用操作，此时dp[i][j] = dp[i-1][j-1]，即此时的最小操作数和word1和word2都减少一个字符的最小编辑数相同
    2. 如果word1[i-1] !== word2[j-1]，则分为三种情况
      1. word1删除最后一个字符，状态转移成dp[i-1][j]，即dp[i][j] = dp[i-1][j] + 1，+1指删除操作
      2. word1在最后加上一个字符，状态转移成dp[i][j-1]，即dp[i][j] = dp[i][j-1] + 1，+1指增加操作
      3. word1替换最后一个字符，状态转移成dp[i-1][j-1]，即dpi = dpi-1 + 1，+1指替换操作
  • 复杂度：时间复杂度是O(mn) ，m是word1的长度，n是word2的长度。空间复杂度是O(mn) ，需要用m * n大小的二维数字存储状态。

Js:

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

312. 戳气球 (hard)

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 numsi - 1 numsi numsi + 1 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。求所能获得硬币的最大数量。示例 1： 输入：nums = 3,1,5,8 输出：167 解释： nums = 3,1,5,8 --> 3,5,8 --> 3,8 --> 8 --> [] coins = 315 + 358 + 138 + 181 = 167 示例 2：输入：nums = 1,5 输出：10提示：n == nums.length 1 <= n <= 300 0 <= numsi <= 100

方法1:动态规划
ds_112
  • 思路：dp[i][j] 表示开区间 (i,j) 能拿到的的金币，k是这个区间 最后一个 被戳爆的气球，枚举i和j，遍历所有区间，i-j能获得的最大数量的金币等于 戳破当前的气球获得的金钱加上之前i-k、k-j区间中已经获得的金币
  • 复杂度：时间复杂度O(n^3)，n是气球的数量，三层遍历。空间复杂度O(n^2)，dp数组的空间。

js：

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

70. 爬楼梯 （medium）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。1 阶 + 1 阶 2 阶示例 2：输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。1 阶 + 1 阶 + 1 阶 1 阶 + 2 阶 2 阶 + 1 阶提示：1 <= n <= 45

方法1.动态规划
ds_71
  • 思路：因为每次可以爬 1 或 2 个台阶，所以到第n阶台阶可以从第n-2或n-1上来，其实就是斐波那契的dp方程
  • 复杂度分析：时间复杂度O(n)，空间复杂度O(1)

Js:

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

343. 整数拆分 (medium)

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。示例 1:输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2:输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。提示:2 <= n <= 58

ds_136
  • 思路：dp[i]为正整数i拆分之后的最大乘积，循环数字n，对每个数字进行拆分，取最大的乘积，状态转移方程：dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j)，j*(i-j)表示把i拆分为j和i-j两个数相乘，j * dp[i-j]表示把i拆分成j和继续把(i-j)这个数拆分，取(i-j)拆分结果中的最大乘积与j相乘
  • 复杂度：时间复杂度O(n^2)，两层循环。空间复杂度O(n)，dp数组的空间

js：

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

64. 最小路径和 (medium)

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例 1：

：因为路径 1→3→1→1→1 的总和最小。 示例 2：输入：grid = [1,2,3,4,5,6] 输出：12提示：m == grid.length n == gridi.length 1 <= m, n <= 200 0 <= gridi <= 100

ds_205
  • 思路：dp[i][j]表示从矩阵左上角到（i，j）这个网格对应的最小路径和，只要从上到下，从左到右遍历网格，当前最小路径和就是当前的数值加上上面和左边左小的。
  • 复杂度：时间复杂度O(mn)，m、n分别是矩阵的长和宽。空间复杂度如果原地修改是O(1)，如果新建dp数组就是O(mn)

js：

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

62. 不同路径 （medium）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

= 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。向右 -> 向下 -> 向下 向下 -> 向下 -> 向右 向下 -> 向右 -> 向下示例 3：输入：m = 7, n = 3 输出：28 示例 4：输入：m = 3, n = 3 输出：6提示：1 <= m, n <= 100 题目数据保证答案小于等于 2 * 109

方法1.动态规划

动画过大，点击查看

  • 思路:由于在每个位置只能向下或者向右， 所以每个坐标的路径和等于上一行相同位置和上一列相同位置不同路径的总和，状态转移方程：f[i][j] = f[i - 1][j] + f[i][j - 1];
  • 复杂度:时间复杂度O(mn)。空间复杂度O(mn)，优化后O(n)

js:

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

0-1背包问题

0-1背包问题指的是有n个物品和容量为j的背包，weight数组中记录了n个物品的重量，位置i的物品重量是weighti，value数组中记录了n个物品的价值，位置i的物品价值是vales[i]，每个物品只能放一次到背包中，问将那些物品装入背包，使背包的价值最大。

举例：

ds_214

我们用动态规划的方式来做

  • 状态定义：dp[i][j] 表示从前i个物品里任意取，放进容量为j的背包，价值总和最大是多少
  • 状态转移方程： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 每个物品有放入背包和不放入背包两种情况
  1. 当j - weight[i]<0：表示装不下i号元素了，不放入背包，此时dp[i][j] = dp[i - 1][j]，dpi取决于前i-1中的物品装入容量为j的背包中的最大价值
  2. 当j - weight[i]>=0：可以选择放入或者不放入背包。 放入背包则：dp[i][j] = dp[i - 1][j - weight[i]] + value[i]， dp[i - 1][j - weight[i]] 表示i-1中的物品装入容量为j-weight[i]的背包中的最大价值，然后在加上放入的物品的价值value[i]就可以将状态转移到dp[i][j]。 不放入背包则：dp[i][j] = dp[i - 1] [j]，在这两种情况中取较大者。
  • 初始化dp数组：dp[i][0]表示背包的容积为0，则背包的价值一定是0，dp[0][j]表示第0号物品放入背包之后背包的价值
ds_137
  • 最终需要返回值：就是dp数组的最后一行的最后一列

循环完成之后的dp数组如下图

ds_138

js：

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();

状态压缩

根据状态转移方程dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，第i行只与第i-1行状态相关，所以我们可以用滚动数组进行状态压缩，其次我们注意到，j只与j前面的状态相关，所以只用一个数组从后向前计算状态就可以了。

动画过大，点击查看

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

416. 分割等和子集 （medium）

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例 1：输入：nums = 1,5,11,5 输出：true 解释：数组可以分割成 1, 5, 5 和 11 。 示例 2：输入：nums = 1,2,3,5 输出：false 解释：数组不能分割成两个元素和相等的子集。提示：1 <= nums.length <= 200 1 <= numsi <= 100

ds_140
  • 思路：本题可以看成是0-1背包问题，给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量记录在 nums 数组中，问是否在一种装法，能够恰好将背包装满？dp[i][j]表示前i个物品是否能装满容积为j的背包，当dp[i][j]为true时表示恰好可以装满。每个数都有放入背包和不放入两种情况，分析方法和0-1背包问题一样。
  • 复杂度：时间复杂度O(n*sum)，n是nums数组长度，sum是nums数组元素的和。空间复杂度O(n * sum)，状态压缩之后是O(sum)

js：

//可以看成是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];
};

买卖股票问题

ds_74

121. 买卖股票的最佳时机（easy）限定交易次数 k=1

122. 买卖股票的最佳时机 II（medium）交易次数无限制 k = +infinity

123. 买卖股票的最佳时机 III (hrad) 限定交易次数 k=2

188. 买卖股票的最佳时机 IV (hard) 限定交易次数 最多次数为 k

309. 最佳买卖股票时机含冷冻期(medium) 含有交易冷冻期

714. 买卖股票的最佳时机含手续费 (medium) 每次交易含手续费

第5，6道题相当于在第2道题的基础上加了冷冻期和手续费的条件。

限制条件
  • 先买入才能卖出
  • 不能同时参加多笔交易，再次买入时，需要先卖出
  • k >= 0才能进行交易，否则没有交易次数
定义操作
  • 买入
  • 卖出
  • 不操作
定义状态
  • i: 天数
  • k: 交易次数，每次交易包含买入和卖出，这里我们只在买入的时候需要将 k - 1
  • 0: 不持有股票
  • 1: 持有股票
举例
  dp[i][k][0]//第i天 还可以交易k次 手中没有股票
  dp[i][k][1]//第i天 还可以交易k次 手中有股票

最终的最大收益是dp[n - 1][k][0]而不是dp[n - 1][k][1]，因为最后一天卖出肯定比持有收益更高

状态转移方程
// 今天没有持有股票，分为两种情况：
// 1. dp[i - 1][k][0]，昨天没有持有，今天不操作。 
// 2. dp[i - 1][k][1] + prices[i] 昨天持有，今天卖出，今天手中就没有股票了。
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])


// 今天持有股票，分为两种情况：
// 1.dp[i - 1][k][1] 昨天持有，今天不操作
// 2.dp[i - 1][k - 1][0] - prices[i] 昨天没有持有，今天买入。
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

//最大利润就是这俩种情况的最大值

121. 买卖股票的最佳时机（easy）限定交易次数 k=1

给定一个数组 prices ，它的第 i 个元素 pricesi 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。示例 1：输入：7,1,5,3,6,4 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2：输入：prices = 7,6,4,3,1 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。提示：1 <= prices.length <= 105 0 <= pricesi <= 104

状态转移方程

//第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后卖出 两种情况的最大值转移过来
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
//第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后买入 两种情况的最大值转移过来
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
            = Math.max(dp[i - 1][1][1], -prices[i]) // k=0时 没有交易次数，dp[i - 1][0][0] = 0

k是固定值1，不影响结果，所以可以不用管，简化之后如下

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], -prices[i])

完整代码

//时间复杂度O(n) 空间复杂度O(n)，dp数组第二维是常数
const maxProfit = function (prices) {
    let n = prices.length;
    let dp = Array.from(new Array(n), () => new Array(2));
    dp[0][0] = 0; //第0天不持有
    dp[0][1] = -prices[0]; //第0天持有
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
    }
    return dp[n - 1][0];
};

状态压缩，dp[i] 只和 dp[i - 1] 有关，去掉一维

//时间复杂度O(n) 空间复杂度O(1)
const maxProfit = function (prices) {
    let n = prices.length;
    let dp = Array.from(new Array(n), () => new Array(2));
    dp[0] = 0;
    dp[1] = -prices[0];
    for (let i = 1; i < n; i++) {
        dp[0] = Math.max(dp[0], dp[1] + prices[i]);
        dp[1] = Math.max(dp[1], -prices[i]);
    }
    return dp[0];
};

//语意化
const maxProfit = function (prices) {
    let n = prices.length;
    let sell = 0;
    let buy = -prices[0];
    for (let i = 1; i < n; i++) {
        sell = Math.max(sell, buy + prices[i]);
        buy = Math.max(buy, -prices[i]);
    }
    return sell;
};

122. 买卖股票的最佳时机 II（medium）交易次数无限制 k = +infinity

给你一个整数数组 prices ，其中 pricesi 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。返回 你能获得的 最大 利润 。示例 1：输入：prices = 7,1,5,3,6,4 输出：7 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。 示例 2：输入：prices = 1,2,3,4,5 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 总利润为 4 。 示例 3：输入：prices = 7,6,4,3,1 输出：0 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。提示：1 <= prices.length <= 3 * 104 0 <= pricesi <= 104

状态转移方程

//第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后卖出 两种情况的最大值转移过来
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
//第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后买入 两种情况的最大值转移过来
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

k同样不影响结果，简化之后如下

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])

完整代码

const maxProfit = function (prices) {
    let n = prices.length;
    let dp = Array.from(new Array(n), () => new Array(2));
    dp[0][0] = 0; //第0天不持有
    dp[0][1] = -prices[0]; //第0天买入 花了prices[0]
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[n - 1][0];
};

状态压缩，同样dp[i] 只和 dpi - 1 有关，去掉一维

const maxProfit = function (prices) {
    let n = prices.length;
    let dp = Array.from(new Array(n), () => new Array(2));
    dp[0] = 0;
    dp[1] = -prices[0];
    for (let i = 1; i < n; i++) {
        dp[0] = Math.max(dp[0], dp[1] + prices[i]);
        dp[1] = Math.max(dp[1], dp[0] - prices[i]);
    }
    return dp[0];
};

//语意化
const maxProfit = function (prices) {
    let n = prices.length;
    let sell = 0;
    let buy = -prices[0];
    for (let i = 1; i < n; i++) {
        sell = Math.max(sell, buy + prices[i]);
        buy = Math.max(buy, sell - prices[i]);
    }
    return sell;
};

123. 买卖股票的最佳时机 III (hrad) 限定交易次数 k=2

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1:输入：prices = 3,3,5,0,0,3,1,4 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。 示例 2：输入：prices = 1,2,3,4,5 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。undefined 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。undefined 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 示例 3：输入：prices = 7,6,4,3,1 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。 示例 4：输入：prices = 1 输出：0提示：1 <= prices.length <= 105 0 <= pricesi <= 105

状态转移方程

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

k对结果有影响 不能舍去，只能对k进行循环

for (let i = 0; i < n; i++) {
  for (let k = maxK; k >= 1; k--) {
    dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
    dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
  }
}


//k=2，直接写出循环的结果
dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])

dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
            = Math.max(dp[i - 1][1][1], -prices[i])// k=0时 没有交易次数，dp[i - 1][0][0] = 0

//去掉i这一维度
dp[2][0] = Math.max(dp[2][0], dp[2][1] + prices[i])
dp[2][1] = Math.max(dp[2][1], dp[1][0] - prices[i])

dp[1][0] = Math.max(dp[1][0], dp[1][1] + prices[i])
dp[1][1] = Math.max(dp[1][1], dp[0][0] - prices[i])
            = Math.max(dp[1][1], -prices[i])// k=0时 没有交易次数，dp[i - 1][0][0] = 0

完整代码

//和前面一样 我们直接降维
const maxProfit = function (prices) {
    let buy_1 = -prices[0], sell_1 = 0
    let buy_2 = -prices[0], sell_2 = 0
    let n = prices.length
    for (let i = 1; i < n; i++) {
        sell_2 = Math.max(sell_2, buy_2 + prices[i])
        buy_2 = Math.max(buy_2, sell_1 - prices[i])
        sell_1 = Math.max(sell_1, buy_1 + prices[i])
        buy_1 = Math.max(buy_1, -prices[i])
    }
    return sell_2
}

188. 买卖股票的最佳时机 IV (hard) 限定交易次数 最多次数为 k

给定一个整数数组 prices ，它的第 i 个元素 pricesi 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1：输入：k = 2, prices = 2,4,1 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。 示例 2：输入：k = 2, prices = 3,2,6,5,0,3 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。提示：0 <= k <= 100 0 <= prices.length <= 1000 0 <= pricesi <= 1000

const maxProfit = function (k, prices) {
    let n = prices.length;
    let profit = new Array(k);//和123题一样 求出所有k的状态
    // 初始化k次交易买入卖出的利润
    for (let j = 0; j <= k; j++) {
        profit[j] = {
            buy: -prices[0],//表示有股票
            sell: 0,//表示没有股票
        };
    }
    for (let i = 0; i < n; i++) {
        for (let j = 1; j <= k; j++) {
            //122题可以交易无数次，188交易k次，所以直接在加一层k循环就可以
              //122最后的递推方程：
              //sell = Math.max(sell, buy + prices[i]);
                //buy = Math.max(buy, -prices[i]);
            profit[j] = {
                sell: Math.max(profit[j].sell, profit[j].buy + prices[i]),
                buy: Math.max(profit[j].buy, profit[j - 1].sell - prices[i]),
            };
        }
    }
    return profit[k].sell; //返回第k次清空手中的股票之后的最大利润
};

309. 最佳买卖股票时机含冷冻期(medium) 含有交易冷冻期

给定一个整数数组prices，其中第 pricesi 表示第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1:输入: prices = 1,2,3,0,2 输出: 3 解释: 对应的交易状态为: 买入, 卖出, 冷冻期, 买入, 卖出 示例 2:输入: prices = 1 输出: 0提示：1 <= prices.length <= 5000 0 <= pricesi <= 1000

状态转移方程

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
//冷却时间1天，所以要从 i - 2 天转移状态
//买入，卖出 ---- 冷冻期 ----  买入，卖出
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])

题目不限制k的大小，可以舍去

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i])

//降维i
dp[0] = Math.max(dp[0], dp[1] + prices[i])
dp[1] = Math.max(dp[1], profit_freeze - prices[i])

完整代码

const maxProfit = function (prices) {
    let n = prices.length;
    let buy = -prices[0];//手中有股票
    let sell = 0;//没有股票
    let profit_freeze = 0;
    for (let i = 1; i < n; i++) {
        let temp = sell;
        sell = Math.max(sell, buy + prices[i]);
        buy = Math.max(buy, profit_freeze - prices[i]);
        profit_freeze = temp;
    }
    return sell;
};

714. 买卖股票的最佳时机含手续费 (medium) 每次交易含手续费

给定一个整数数组 prices，其中 pricesi表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。示例 1：输入：prices = 1, 3, 2, 8, 4, 9, fee = 2 输出：8 解释：能够达到的最大利润:undefined在此处买入 prices0 = 1 在此处卖出 prices3 = 8 在此处买入 prices4 = 4 在此处卖出 prices5 = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8 示例 2：输入：prices = 1,3,7,5,10,3, fee = 3 输出：6提示：1 <= prices.length <= 5 104 1 <= pricesi < 5 104 0 <= fee < 5 * 104

状态转移方程

//每次交易要支付手续费 我们定义在卖出的时候扣手续费
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

完整代码

const maxProfit = function (prices, fee) {
    let sell = 0;//卖出
    let buy = -prices[0];//买入
    for (let i = 1; i < prices.length; i++) {
        sell = Math.max(sell, buy + prices[i] - fee);
        buy = Math.max(buy, sell - prices[i]);
    }
    return sell;
};

322. 零钱兑换 (medium)

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。示例 1：输入：coins = 1, 2, 5, amount = 11 输出：3 解释：11 = 5 + 5 + 1 示例 2：输入：coins = 2, amount = 3 输出：-1 示例 3：输入：coins = 1, amount = 0 输出：0提示：1 <= coins.length <= 12 1 <= coinsi <= 231 - 1 0 <= amount <= 104

ds_75

不能用贪心做，反例，coins=[1, 3, 5, 6, 7]，amount=30，用贪心先用最大的面额7，在用2个1，4 * 7 + 2 * 1 = 30，但是我们用5个6，5 * 6 = 30 就能用最少的硬币兑换完成

方法1.动态规划

  • 思路：dp[i]表示兑换面额i所需要的最少硬币，因为硬币无限，所以可以自底向上计算dp[i]，对于dp[0~i]的每个状态，循环coins数组，寻找可以兑换的组合，用i面额减去当前硬币价值，dp[i-coin]在加上一个硬币数就是dp[i],最后取最小值就是答案，状态转移方程就是dp[i] = Math.min(dp[i], dp[i - coin] + 1);
  • 复杂度分析：时间复杂度是O(sn)，s是兑换金额，n是硬币数组长度，一共需要计算s个状态，每个状态需要遍历n个面额来转移状态。空间复杂度是O(s)，也就是dp数组的长度

Js:

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

63. 不同路径 II（medium）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。示例 1：

输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：向右 -> 向右 -> 向下 -> 向下 向下 -> 向下 -> 向右 -> 向右示例 2：
== obstacleGrid.length n == obstacleGridi.length 1 <= m, n <= 100 obstacleGridi 为 0 或 1

方法1.动态规划
  • 思路：和62题一样，区别就是遇到障碍直接返回0
  • 复杂度：时间复杂度O(mn)，空间复杂度O(mn)，状态压缩之后是o(n)

Js:

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

视频讲解：传送门

相关文章