大厂算法面试之leetcode精讲3.动态规划

作者: 全栈潇晨 | 来源:发表于2021-11-22 08:24 被阅读0次

大厂算法面试之leetcode精讲3.动态规划

视频教程（高效学习）:点击学习

什么是动态规划

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

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

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

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

动态规划的解题方法

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

ds_135

解动态规划题目的步骤

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

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

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] = fib(x - 1) + fib(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）

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

Java:

class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int prev2 = 0, prev1 = 1, result = 0;
        for (int i = 2; i <= n; i++) {
            result = prev2 + prev1;
            prev2 = prev1; 
            prev1 = result; 
        }
        return result;
    }
}

62. 不同路径（medium）

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

Java:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}

//状态压缩
class Solution {
    public int uniquePaths(int m, int n) {
        int[] cur = new int[n];
        Arrays.fill(cur,1);
        for (int i = 1; i < m;i++){
            for (int j = 1; j < n; j++){
                cur[j] += cur[j-1] ;
            }
        }
        return cur[n-1];
    }
}

63. 不同路径 II（medium）

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

Java:

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] dp = new int[m];

        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        
        return dp[m - 1];
    }
}

70. 爬楼梯（medium）

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

Java:

class Solution {
    public int climbStairs(int n) {
        int prev = 1, cur = 1;
        for (int i = 2; i < n + 1; i++) {
        int temp = cur;
        cur = prev + cur;  
        prev = temp; 
        }
        return cur;
    }
}

279. 完全平方数 (medium)

ds_204

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

java：

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n];
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; i - j * j >= 0; j++) { 
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

120. 三角形最小路径和（medium）

方法1.动态规划

ds_72

思路：从三角形最后一层开始向上遍历，每个数字的最小路径和是它下面两个数字中的较小者加上它本身
复杂度分析：时间复杂度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];
};

Java:

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int [] dp = new int [n];
        for(int i = 0 ; i < n ; i++){
            dp[i] = triangle.get(n-1).get(i);
        }
        for(int i = n-2 ; i >= 0 ; i--){
            for(int j = 0 ; j <= i ; j++){
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j] , dp[j+1]);//迭代
            }
        }
        return dp[0];
    }
}

152. 乘积最大子数组（medium）

方法1.动态规划

ds_73

思路：
1. 状态定义：dp[i][0]表示从第 0 项到第 i 项范围内的子数组的最小乘积，dp[i][1]表示从第 0 项到第 i 项范围内的子数组的最大乘积
2. 初始状态：dp[0][0]=nums[0], dp[0][1]=nums[0]
3. 分情况讨论:
  - 不和别人乘，就 nums[i]自己
  - num[i] 是负数，希望乘上前面的最大积
  - num[i] 是正数，希望乘上前面的最小积
4. 状态转移方程：
  - 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])
5. 状态压缩：dp[i][x]只与dp[i][x]-1，所以只需定义两个变量，prevMin = nums[0]，prevMax = nums[0]
6. 状态压缩之后的方程：
  - 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
}

Java:

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

买卖股票问题

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

状态转移方程

//第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

状态转移方程

//第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

状态转移方程

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

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) 含有交易冷冻期

状态转移方程

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) 每次交易含手续费

状态转移方程

//每次交易要支付手续费 我们定义在卖出的时候扣手续费
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)

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

Java:

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

72. 编辑距离（hard）

方法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]，即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];
};

Java:

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        dp[i][0] =  i;
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
    }
    return dp[m][n];
}

大厂算法面试之leetcode精讲3.动态规划