全栈大前端

# 概念

  • 最优判断+回退

# 应用场景

  • 解决最值问题

  • 最优子结构

  • 重叠子问题

# 思维分析

  • 步骤

  1. 递归+记忆化 -> 递推

  2. 状态定义：opt[n],dp[n],fib[n]

  3. 状态转移方程：opt[n]= best_of(opt[n-1],opt[n-2],...)

  4. 最优子结构

  • 难点

  1. 状态转移方程不好确定

  2. 已知的状态可能不明显

  3. 递归转迭代，一部分同学可能不知道怎么转（这个就是纯粹的编程基础问题了，多写多练哈）

  • 分析方法
  1. 递归思想明确树形思维模型：找到问题终点，思考倒退的姿势，往往可以帮助你更快速地明确状态间的关系
  2. 结合记忆化搜索，明确状态转移方程
  3. 递归代码转化为迭代表达（这一步不一定是必要的，1、2本身为思维路径，而并非代码实现。若你成长为熟手，2中分析出来的状态转移方程可以直接往循环里塞，根本不需要转换）。

# 高频题

# 爬楼梯 (简单)

  • 递推公式 f(n)=f(n-1)+ f(n-2)
const climbStairs =function (n){
    // 初始化状态数组
    const f =[];
    // 初始化已知值
    f[1] = 1;
    f[2] = 2;

    // 动态更新每一层楼梯对应的结果
    for(let i =3; i<=n; i++){
        f[i] =f[i-2] +f[i-1]
    }
    // 返回目标值
    return f[n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 最少的硬币数目（中等）

  • 递推公式 f(36) = Math.min(f(36-c1)+1,f(36-c2)+1,f(36-c3)+1......f(36-cn)+1)
const coinChange =function (coins,amount){
    // 用于保存每个目标总额对应的最小硬币个数
    const f = []
    // 提前定义已知情况
    f[0] =0
    //遍历 [1,amount] 这个区间的硬币总额
    for (let i =1; i<= amount;i++){
        //求的最小值，因此我们预设为无穷大，确保它一定会被更小的数更新
        f[i]=Infinity
        //循环 遍历每个可用硬币的面额
        for(let j =0;j<coins.length;j++){
            //若硬币面额小于目标总额，则问题成立
            if(i-coins[j]>=0){
                //状态转移方程
                f[i]=Math.min(f[i],f[i-coins[j]]+1)
            }
        }
    }
    //若目标总额对应的解为无穷大，则意味着没有一个符合条件的硬币总数来更新它，本题无解，返回-1
    if(f[amount]===Infinity){
        return -1
    }
    //若有解，直接返回解的内容
    return f[amount]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 剪绳子(中等) (opens new window)

  • 状态转移方程:dp[i] = Math.max(dp[i], (i - j) * j, dp[i - j] * j)
  1. dp[i]含义：拆分数字i，可得到最大的乘积为dp[i]
  2. 递推公式：对于某一个i，用j从1遍历到i-1：
  • (i-j)*j表示拆分成2个数
  • dp[i-j]*j表示拆分成2个及以上的数
  • 因为j在遍历的过程中，会算出很多dp[i]，取三者最大的
  • 所以dp[i] = Math.max(dp[i], (i - j) * j, dp[i - j] * j)
  1. dp[i]初始化：n=0和n=1没有意义，dp[2]=1，所以直接初始化dp = [null, null, 1]
  2. 从前向后遍历
const cuttingRope = n => {
    const dp =[null,null,1];
    for(let i =3 ; i<=n; i++){
        //当前dp[i]初始化为0
        dp[i]=0
        for(let j=1; j <= i-1; j++){
            //因为j在遍历打过程中，会算出很多dp[i],取最大的
            //（i-j）*j 表示拆分成2个数
            // dp[i-j] *j 表示拆分成2个及以上的数
            dp[i] = Math.max(dp[i],(i-j) * j,dp[i-j]*j);
        }
    }
    return dp[n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 背包问题

# [0-1背包问题]

最基本的背包问题就是01背包问题（01 knapsack problem）：一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

  • 状态转移方程: dp[i][v]=Math.max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
// 入参是物品的个数和背包的容量上限，以及物品的重量和价值数组
function knapsack(n,c,w,value){
    // dp 是动态规划的状态保存数组
    const dp=(new Array(c+1)).fill(0)
    // res 用来记录所有组合方案中的最大值
    let res =Infinity
    for(let i=1;i<=n;i++){
        for(let v=c;v>=w[i];v--){
            // 写出状态转移方程
            dp[v]=Math.max(dp[v],dp[v-w[i]+value[i]])
            // 即时更新最大值
            if(dp[v]>res){
                res= dp[v]
            }   
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 完全背包问题：零钱兑换(中等) (opens new window)

  • dp[0] = 0 金额为零时不需要硬币

  • dp[n] = min(dp[n],dp[n-coin1] + 1，dp[n-coin2],...) 金额为n时，硬币数等于(n-coin)+1中所需硬币最少的组合

const coinChange =function (coins,amount){
    let dp =new Array(amount +1).fill(Infinity);
    dp[0] =0;
    for(let i =1;i <= amount; i++){
        for(let coin of coins){
            if(i -coin >=0)
            {
                dp[i]=Math.min(dp[i],dp[i-coin]+1);
            }
        }
    }
    return dp[amount] ===Infinity? -1:dp[amount]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 多重背包问题：零钱兑换II(中等) (opens new window)

var change = function(amount, coins) {

if (amount === 0) return 1;

const dp = [Array(amount + 1).fill(1)];

for (let i = 1; i < amount + 1; i++) {
  dp[i] = Array(coins.length + 1).fill(0);
  for (let j = 1; j < coins.length + 1; j++) {
    // 从1开始可以简化运算
    if (i - coins[j - 1] >= 0) {
      // 注意这里是coins[j -1]而不是coins[j]
      dp[i][j] = dp[i][j - 1] + dp[i - coins[j - 1]][j]; // 由于可以重复使用硬币所以这里是j不是j-1
    } else {
      dp[i][j] = dp[i][j - 1];
    }
  }
}

return dp[dp.length - 1][coins.length];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 买卖股票类问题

  1. 第一题只交易一次，也就是 k = 1。
  2. 第二题不限制交易次数，也就是 k = +infinity。
  3. 第三题只交易两次，也就是 k = 2。
  4. 第四道限制最多次数为 k。
  5. 第五道和第六道不限次数，相当于在第二题的基础上分别添加了交易冷冻期和手续费的额外条件。

# 买卖股票的最佳时机(简单) (opens new window)

const maxProfit=function (prices){
    let n =prices.length
    let profit_out =0
    let profit_in = -prices[0]
    for(let i =1;i<n;i++){
        profit_out =Math.max(profit_out,profit_in +prices[i])
        //k=1时，及交易次数为1时， 买入时的利润都是 -prices[i]
        profit_in =Math.max(profit_in,-prices[i])
    }
    return profit_out
}
//时间复杂度：O(n)
//空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 买卖股票的最佳时机II(中等) (opens new window)

const maxProfit = function(prices) {
    let n = prices.length
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < n; i++) {
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in, profit_out - prices[i])
    }
    return profit_out
}
1
2
3
4
5
6
7
8
9
10

# 买卖股票的最佳时机III(困难) (opens new window)

var maxProfit = function(prices) {
    //第一次 买入， 卖出的利润
    let profit_1_in = -prices[0], profit_1_out = 0;
    //继第一次之后，第二次买入卖出的利润
    let profit_2_in = -prices[0], profit_2_out = 0;
    let n = prices.length;
    for (let i = 1; i < n; i++){
        profit_2_out = Math.max(profit_2_out, profit_2_in + prices[i]);
        //第二次买入后的利润， 第一次卖出的利润 - prices[i]
        profit_2_in = Math.max(profit_2_in, profit_1_out - prices[i]);
        profit_1_out = Math.max(profit_1_out, profit_1_in + prices[i]);
        //第一次买入后，利润为 -prices[i]
        profit_1_in = Math.max(profit_1_in, -prices[i]);
    }
    return profit_2_out;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 买卖股票的最佳时机IV(困难) (opens new window)

const maxProfit = function(k, prices) {
    let n = prices.length;
    if (k > n / 2) {
        k = Math.floor(n/2);  //这样也可以，但其实增加了时间复杂度和内存消耗
        // return maxProfit_k_infinity(prices); //也可以
    }
    let profit = new Array(k);
    //初始化买入卖出时的利润
    for (let j = 0; j <= k; j++){
        profit[j] = {
            profit_in: -prices[0],
            profit_out: 0
        };
    }
    for (let i = 0; i < n; i++){
        for (let j = 1; j <= k; j++){
            profit[j] = {
                profit_out: Math.max(profit[j].profit_out, profit[j].profit_in + prices[i]), 
                profit_in: Math.max(profit[j].profit_in, profit[j-1].profit_out - prices[i])
            }
        }
    }
    return profit[k].profit_out;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 最佳买卖股票时机含冷冻期(中等) (opens new window)

var maxProfit = function(prices) {
    let n = prices.length;
    let profit_in = 0 - prices[0];
    let profit_out = 0;
    //冻结时的利润
    let profit_freeze = 0;
    for (let i = 1; i < n; i++){
        let temp = profit_out;
        profit_out = Math.max(profit_out, profit_in + prices[i]);
        //买入时的利润= 上次冻结时的利润 - 当天价格
        profit_in = Math.max(profit_in, profit_freeze - prices[i]);
        //冻结时的利润 = 上次卖出时的利润
        profit_freeze = temp;
    }
    return profit_out;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 买卖股票的最佳时机含手续费(中等) (opens new window)

var maxProfit = function(prices, fee) {
    //初始利润
    var profit_in = 0 - prices[0];
    var profit_out = 0;
    for (let i = 1; i < prices.length; i++){
        //卖出： 当前买入状态时的利润 + 卖出的股票 - 手续费
        profit_out = Math.max(profit_out ,profit_in + prices[i] - fee); 
        //买入： 当前卖出时的利润 - 买进的股票
        profit_in = Math.max(profit_in ,profit_out - prices[i]);     
    }
    return profit_out;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# 参考链接:

一口气团灭6道股票算法 (opens new window) 买卖股票最佳时机6道题解 (opens new window)

# 打家劫舍问题

# 打家劫舍I(中等) (opens new window)

  • 状态转移方程：dp[n] = MAX( dp[n-1], dp[n-2] + num )

  1. 由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 房屋可盗窃的最大值，要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值

  2. 举例来说：1 号房间可盗窃最大值为 33 即为 dp[1]=3，2 号房间可盗窃最大值为 44 即为 dp[2]=4，3 号房间自身的值为 22 即为 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5，3 号房间可盗窃最大值为 55

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const len = nums.length;
    if(len == 0)
        return 0;
    const dp = new Array(len + 1);
    dp[0] = 0;
    dp[1] = nums[0];
    for(let i = 2; i <= len; i++) {
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
    }
    return dp[len];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 子序列问题

# 最长递增子序列(中等) (opens new window)

# 解法一 ：动态规划

  • 概念理解:
  1. 子串：一定是连续的
  2. 子序列：子序列不要求连续 例如：[6, 9, 12] 是 [1, 3, 6, 8, 9, 10, 12] 的一个子序列
  3. 上升/递增子序列：一定是严格上升/递增的子序列
  • 状态转移方程:
  1. 当我们遍历 nums[i] 时，需要同时对比已经遍历过的 nums[j]
  2. 如果 nums[i] > nums[j]，nums[i] 就可以加入到序列 nums[j] 的最后，长度就是 dp[j] + 1 注：(0 <= j < i) (nums[j] < nums[i])
const lengthOfLIS = function(nums) {
    let n = nums.length
    if (n == 0) {
        return 0
    }
    let dp = new Array(n).fill(1)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp) 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 解法二：贪心+二分查找

  1. 这里再结合本题理解一下贪心思想，同样是长度为 2 的序列，[1,2] 一定比 [1,4] 好，因为它更有潜力。换句话说，我们想要组成最长的递增子序列，就要让这个子序列中上升的尽可能的慢，这样才能更长。

  2. 我们可以创建一个 tails 数组，用来保存最长递增子序列，如果当前遍历的 nums[i] 大于 tails 的最后一个元素(也就是 tails 中的最大值)时，我们将其追加到后面即可。否则的话，我们就查找 tails 中第一个大于 nums[i] 的数并替换它。因为是单调递增的序列，我们可以使用二分查找，将时间复杂度降低到 O(logn)

const lengthOfLIS =function (nums){
    let len = nums.length
    if(len <=1){
        return len
    }
    let tails =[nums[0]]
    for(let i =0;i<len;i++){
        //当前遍历元素nums[i]大于前一个递增子序列的尾元素时,追加到后面即可
        if(nums[i] >tails[tails.length -1]){
            tails.push(nums[i])
        }else{
            //否则，查找递增子序列中第一个大于当前值的元素，用当前遍历元素nums[i]替换它
            //递增序列，可以使用二分查找
            let left = 0;
            let right =tails.length -1
            while(left<right){
                let mid =(left+ right)>>1;
                if(tails[mid]<nums[i]){
                    left =mid+1
                }else{
                    right =mid
                }
            }
            tails[left]=nums[i]
        }
    }
    return tails.length
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 最长回文子序列(中等) (opens new window)

  • 状态转移方程:

s[i] === s[j] && dp[i][j] = dp[i+1][j-1]

const longestPalindrome =function (s){
    const len =s.length
    const dp= Array.from(new Array(len),()=> new Array(len).fill(0))
    let res =''
    for(let i =len-1; i>=0;i--){
        for(let j=i; j<len;j++){    
            dp[i][j]= s[i]===s[j]&&(j-i<2 || dp[i+1][j-1])
            if(dp[i][j]&&j-i+1>res.length){
                res=s.slice(i,j+1)
            }
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 最长公共子序列(中等) (opens new window)

var longestCommonSubsequence = function(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        const c1 = text1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = text2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 最长重复子数组(中等) (opens new window)

  1. dp[i][j]含义：以下标i-1为结尾的nums1，和以下标j-1为结尾的nums2，最⻓重复⼦数组⻓度为dp[i][j]
  2. 递推公式：若nums1[i - 1] === nums2[j - 1]，则dp[i][j] = dp[i - 1][j - 1] + 1
  3. dp初始化：dp[i][j]全都初始化为0
const findLength = (nums1, nums2) => {
    const [m, n] = [nums1.length, nums2.length];
    const dp = [];
    // dp数组初始化
    // 先让所有元素为0
    for (let i = 0; i <= m; i++) {
        dp[i] = [];
        for (let j = 0; j <= n; j++) {
            dp[i].push(0);
        }
    }

    let res = 0;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (nums1[i - 1] === nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            res = dp[i][j] > res ? dp[i][j] : res;
        }
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 鸡蛋掉落(困难) (opens new window)

  • 状态转移方程：dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1
  1. dp[i][j - 1]：楼上的楼层数，鸡蛋没碎 i 不变，扔鸡蛋次数 j 减 1
  2. dp[i - 1][j - 1]： 楼下的楼层数，鸡蛋碎了 i - 1，同时扔鸡蛋次数 j 减 1
//观察状态转移方程，状态转移方程中 [j - 1] 可以省略，所以得出：

//dp[i] = dp[i] + dp[i - 1] + 1

//dp[i]：表示当前次数下使用 i 个鸡蛋可以测出的最高楼层

//while 循环的结束条件是 dp[K][j] < N， 表示 K 个鸡蛋，测试 j 次，最坏情况下最多可以测试 N 层楼。

const superEggDrop = function(K, N) {
    const dp = new Array(K + 1).fill(0)
    let steps = 0
    while (dp[K] < N) {
        steps++
        for (let i = K; i > 0; i--) {
            dp[i] = dp[i] + dp[i - 1] + 1
        }
    }
    return steps
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

← 高频合集 →