写点什么

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

作者:Geek_07a724
  • 2022-11-18
    浙江
  • 本文字数:15326 字

    阅读完需:约 50 分钟

什么是动态规划

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


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

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

  1. 动态规划和分治的区别:动态规划和分治都有最优子结构 ,但是分治的子问题不重叠

  2. 动态规划和贪心的区别:动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优解,所以它永远是局部最优,但是全局的解不一定是最优的。

  3. 动态规划和递归的区别:递归和回溯可能存在非常多的重复计算,动态规划可以用递归加记忆化的方式减少不必要的重复计算

动态规划的解题方法

  • 递归+记忆化(自顶向下)

  • 动态规划(自底向上)


解动态规划题目的步骤

  1. 根据重叠子问题定义状态

  2. 寻找最优子结构推导状态转移方程

  3. 确定 dp 初始状态

  4. 确定输出值

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


动画过大,点击查看


暴力递归


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

509. 斐波那契数(easy)

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,F(1) = 1F(n) = F(n - 1) + F(n - 2),其中 n > 1 给定 n ,请计算 F(n) 。

 

示例 1:

输入:n = 2 输出:1 解释:F(2) = F(1) + F(0) = 1 + 0 = 1 示例 2:

输入:n = 3 输出:2 解释:F(3) = F(2) + F(1) = 1 + 1 = 2 示例 3:

输入:n = 4 输出:3 解释:F(4) = F(3) + F(2) = 2 + 1 = 3 

提示:

0 <= n <= 30

方法 1.动态规划
  • 思路:自底而上的动态规划

  • 复杂度分析:时间复杂度O(n),空间复杂度O(1)


Js:


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 <= 500word1 和 word2 由小写英文字母组成

方法 1.动态规划



  • 思路:dp[i][j] 表示 word1 前 i 个字符和 word2 前 j 个字符的最少编辑距离。

  • 如果word1[i-1] === word2[j-1],说明最后一个字符不用操作,此时dp[i][j] = dp[i-1][j-1],即此时的最小操作数和 word1 和 word2 都减少一个字符的最小编辑数相同

  • 如果word1[i-1] !== word2[j-1],则分为三种情况

  • word1 删除最后一个字符,状态转移成dp[i-1][j],即dp[i][j] = dp[i-1][j] + 1,+1 指删除操作

  • word1 在最后加上一个字符,状态转移成dp[i][j-1],即dp[i][j] = dp[i][j-1] + 1,+1 指增加操作

  • word1 替换最后一个字符,状态转移成dp[i-1][j-1],即 dp[i] [j] = dp[i-1] [j-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];};
复制代码

279. 完全平方数 (medium)

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

 

示例 1:

输入:n = 12 输出:3 解释:12 = 4 + 4 + 4 示例 2:

输入:n = 13 输出:2 解释:13 = 4 + 9 提示:

1 <= n <= 104


方法 1:动态规划
  • 思路:dp[i] 表示i的完全平方和的最少数量,dp[i - j * j] + 1表示减去一个完全平方数j的完全平方之后的数量加 1 就等于dp[i],只要在dp[i], dp[i - j * j] + 1中寻找一个较少的就是最后dp[i]的值。

  • 复杂度:时间复杂度O(n* sqrt(n)),n是输入的整数,需要循环n次,每次计算dp方程的复杂度sqrt(n),空间复杂度O(n)



js:


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];};
复制代码

120. 三角形最小路径和(medium)

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。

 

示例 1:

输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]输出:11 解释:如下面简图所示: 2 3 4 6 5 74 1 8 3 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。示例 2:

输入:triangle = [[-10]]输出:-10 

提示:

1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104 

方法 1.动态规划


  • 思路:从三角形最后一层开始向上遍历,每个数字的最小路径和是它下面两个数字中的较小者加上它本身

  • 复杂度分析:时间复杂度O(n^2),空间复杂O(n)


Js:


const minimumTotal = (triangle) => {    const h = triangle.length;    // 初始化dp数组    const dp = new Array(h);    for (let i = 0; i < h; i++) {        dp[i] = new Array(triangle[i].length);    }
for (let i = h - 1; i >= 0; i--) { //自底而上遍历 for (let j = 0; j < triangle[i].length; j++) { //同一层的 if (i == h - 1) { // base case 最底层 dp[i][j] = triangle[i][j]; } else { // 状态转移方程,上一层由它下面一层计算出 dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]; } } } return dp[0][0];};

//状态压缩const minimumTotal = (triangle) => { const bottom = triangle[triangle.length - 1]; const dp = new Array(bottom.length); // base case 是最后一行 for (let i = 0; i < dp.length; i++) { dp[i] = bottom[i]; } // 从倒数第二列开始迭代 for (let i = dp.length - 2; i >= 0; i--) { for (let j = 0; j < triangle[i].length; j++) { dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j]; } } return dp[0];};
复制代码

买卖股票问题

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 个元素 prices[i] 表示一支给定股票第 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 <= 1050 <= prices[i] <= 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 ,其中 prices[i] 表示某支股票第 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 * 1040 <= prices[i] <= 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] 只和 dp[i - 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 。     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。     因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。示例 3:

输入:prices = [7,6,4,3,1] 输出:0 解释:在这个情况下, 没有交易完成, 所以最大利润为 0。示例 4:

输入:prices = [1]输出:0 

提示:

1 <= prices.length <= 1050 <= prices[i] <= 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 个元素 prices[i] 是一支给定的股票在第 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 <= 1000 <= prices.length <= 10000 <= prices[i] <= 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,其中第  prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

 

示例 1:

输入: prices = [1,2,3,0,2]输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]示例 2:

输入: prices = [1]输出: 0 

提示:

1 <= prices.length <= 50000 <= prices[i] <= 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])
//降维idp[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,其中 prices[i]表示第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。

 

示例 1:

输入:prices = [1, 3, 2, 8, 4, 9], fee = 2 输出:8 解释:能够达到的最大利润:

在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8 示例 2:

输入:prices = [1,3,7,5,10,3], fee = 3 输出:6 

提示:

1 <= prices.length <= 5 * 1041 <= prices[i] < 5 * 1040 <= 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;};
复制代码

152. 乘积最大子数组 (medium)

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

 

示例 1:

输入: nums = [2,3,-2,4]输出: 6 解释: 子数组 [2,3] 有最大乘积 6。示例 2:

输入: nums = [-2,0,-1]输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 

提示:

1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

方法 1.动态规划


  • 思路:

  • 状态定义:dp[i][0]表示从第 0 项到第 i 项范围内的子数组的最小乘积,dp[i][1]表示从第 0 项到第 i 项范围内的子数组的最大乘积

  • 初始状态:dp[0][0]=nums[0], dp[0][1]=nums[0]

  • 分情况讨论:

  • 不和别人乘,就 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])

  • 状态压缩:dp[i][x]只与dp[i][x]-1,所以只需定义两个变量,prevMin = nums[0]prevMax = nums[0]

  • 状态压缩之后的方程:

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

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

  • 复杂度:时间复杂度O(n),空间复杂度O(1)


js:


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}
复制代码

62. 不同路径 (medium)

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

 

示例 1:

输入:m = 3, n = 7 输出:28 示例 2:

输入:m = 3, n = 2 输出:3 解释:从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向下 -> 向下

  2. 向下 -> 向下 -> 向右

  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];};
复制代码

10. 正则表达式匹配(hard)

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符'*' 匹配零个或多个前面的那一个元素所谓匹配,是要涵盖 整个 字符串 s 的,而不是部分字符串。

 示例 1:

输入:s = "aa", p = "a"输出:false 解释:"a" 无法匹配 "aa" 整个字符串。示例 2:

输入:s = "aa", p = "a*"输出:true 解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。示例 3:

输入:s = "ab", p = "."输出:true 解释:"." 表示可匹配零个或多个('*')任意字符('.')。 

提示:

1 <= s.length <= 201 <= p.length <= 30s 只包含从 a-z 的小写字母。p 只包含从 a-z 的小写字母,以及字符 . 和 *。保证每次出现字符 * 时,前面都匹配到有效的字符

方法 1.动态规划



  • 思路:dp[i][j] 表示 s 的前 i 个字符能否和 p 的前 j 个字符匹配,分为四种情况,看图

  • 复杂度:时间复杂度O(mn),m,n 分别是字符串 s 和 p 的长度,需要嵌套循环 s 和 p。空间复杂度O(mn),dp 数组所占的空间


js:


//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串};
复制代码

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 <= 121 <= coins[i] <= 231 - 10 <= amount <= 104



不能用贪心做,反例,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,则无法兑换};
复制代码

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



  • 思路: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];};
复制代码


视频讲解:传送门


用户头像

Geek_07a724

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

评论

发布
暂无评论
用javascript分类刷leetcode3.动态规划(图文视频讲解)_JavaScript_Geek_07a724_InfoQ写作社区