动态规划

解决的问题: 重叠子问题 无后效性的问题

解题的本质: 递归(思想) + 记忆化搜索DP(工具) + 递推(实现)

获得无后效性: 状态定义增加维度 状态定义更细致准确

获得递推公式: 状态定义消除后效性, 转变成小问题, 得到递推

无后效性: 当前状态仅依赖前面状态确定, 不依赖历史的路径未来的选择

贪心每次选最优解，与上一个状态无关

确定dp数组含义
确定递推公式
确定dp初始值
确定遍历顺序
举例推导dp数组

路径问题背包问题打家劫舍股票问题子序列问题

leetcode

技巧

关键在于如何将问题转化定义成 无后效性 重叠子问题

无后效性:定义dp, 减小dp负责的范围, 如以nums[i]为结尾
无后效性:定义dp, 状态定义增加维度, 如买入与不买入
递推公式:动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。
递推公式:尝试递归思路，倒推得到子问题

基础问题

509. 斐波那契数

leetcode

var fib = function(n) {
    const dp = [0,1]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
};

70. 爬楼梯

leetcode

var climbStairs = function(n) {
    const dp = new Array(n).fill(0)
    dp[0] = 1
    dp[1] = 1
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
};

746. 使用最小花费爬楼梯

leetcode

var minCostClimbingStairs = function(cost) {
    // 从大往小思考，主要是为了方便把递归翻译成递推
    // 动态规划有「选或不选」和「枚举选哪个」两种基本思考方式
    // 0 和 1 无需花费
    // 思考递归的过程是怎么写的，就是递推公式
    const n = cost.length;
    const f = Array(n + 1).fill(0);
    for (let i = 2; i <= n; i++) {
        f[i] = Math.min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
    }
    return f[n];
};
// 优化空间复杂度，因为dp[i]就是由前两位推出来的，那么也不用dp数组了
var minCostClimbingStairs = function(cost) {
    let before = after = 0
    for(let i = 2; i <= cost.length; i++) {
        const now =  Math.min(after + cost[i-1], before + cost[i-2])
        before = after
        after = now
    }
    return after
};

62. 不同路径

leetcode

var uniquePaths = function (m, n) {
    // dp[i][j] 到达 i j 有多少种走法，抛弃0 0，从 1 1 开始
    // dp[i][j] = dp[i-1][j] + dp[i][j-1],要走到ij,必须走到i-1 或 j-1。
    // 从[1,1] 走到 [m,n] 需要初始化第一行及第一列为1
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(1))
    for (let i = 2; i <= m; i++) {
        for (let j = 2; j <= n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }

    return dp[m][n]
};

var uniquePaths = function (m, n) {
    const dp = new Array(n + 1).fill(1);
    for (let i = 2; i <= m; i++) {
        for (let j = 2; j <= n; j++) {
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[n];
};

63. 不同路径 II

leetcode

var uniquePathsWithObstacles = function (obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = Array(m).fill(0).map(() => Array(n).fill(0));

    // 初始化第一行及第一列为1，如果障碍物恰巧在这，则行列后续均为0
    for (let i = 0; i < m && !obstacleGrid[i][0]; i++) dp[i][0] = 1;
    for (let j = 0; j < n && !obstacleGrid[0][j]; j++) dp[0][j] = 1;

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j]) continue;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
};
// 2
console.log(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]]));

一维解法

var uniquePathsWithObstacles = function (obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = Array(n).fill(0);
    dp[0] = 1;
    // 要从 i=0 j=0开始完成初始化, 一样能做到石头开始全为0
    for (let i = 0; i < m; i++) {
        // 如果石头在j0列，则j0列后续会一直是0
        if (obstacleGrid[i][0]) dp[0] = 0;
        for (let j = 1; j < n; j++) {
            // 这里不能continue，因为一维这里会有数，要清0
            if (obstacleGrid[i][j]) dp[j] = 0;
            else dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[n - 1];
};
// 2
console.log(uniquePathsWithObstacles([[0, 0, 0], [0, 1, 0], [0, 0, 0]]));

343. 整数拆分

leetcode

// 递归问题: f(n) = max(1 * f(n - 1), 2 * f(n - 2), ..., (n - 1) * f(1))。
var integerBreak = function (n) {
    // dp[i] 拆分 i 能得到的最大乘积，i 从 0 到 n
    // dp[i] = 遍历到j时，j是必拆。此时存在两种情况
    //  j * (i - j): 剩余的数不拆
    //j * dp[i - j]: 剩余的数也拆(j*剩余数拆的最大值)
    //        dp[i]: 得是 j 遍历的循环中的最大值，所以 是三者取最大
    // dp[0]无意义 dp[1]无意义 均无法拆分 dp[2] = 1，其他得赋值0
    let dp = new Array(n + 1).fill(0)
    dp[2] = 1
    for (let i = 3; i <= n; i++) {
        // 对于每个i，遍历其 先拆出j能得的最大值，遍历完j后得到当前i能拆出的最大乘积
        // 至少拆出两个数，两个数遍历到拆一半的时候肯定是最大的，
        // 进一步假设是拆出三个数，那应该遍历到1/3就行，到1/2肯定够
        // 所以j <= i / 2
        // 这里是j<= i/2, 不是<, 不是n/2
        for (let j = 1; j <= i / 2; j++) {
            dp[i] = Math.max(j * (i - j), j * dp[i - j], dp[i])
        }
    }
    return dp[n]
};
// 问题来了，什么时候要一重循环，什么时候要二重循环？
// 那就是内部得多遍历一层，内部可能两种情况，三种情况，k种情况
// 这k种情况也依赖上一次的选择，总体有点像动态规划里再动态规划

function integerBreak(n) {
    if (n === 2) return 1;
    if (n === 3) return 2;

    let result = 1;
    while (n > 4) {
        result *= 3;
        n -= 3;
    }
    result *= n;
    return result;
}

数学解法,连续实数问题: 连续版用微积分可得, 等份时极大点在 e ≈ 2.718

即贪心解法: 尽量切出3, 余5切出3*2, 余4切出2*2(相当于余4不切)

背包问题

1.是排序问题还是组合问题？(外层循环是物品i还是容量j？)

组合问题不考虑顺序，固定顺序，外层循环为遍历物品i
排序问题考虑顺序，外层循环为遍历容量j

2.是完全背包问题，还是01背包问题?(内层循环是正序还是倒序？)

完全背包物品i数量无限，01背包物品仅存在两种状态

01背包不重复计算当前物品i，内层容量j从后往前循环
完全背包重复计算当前物品i，内层容量j从前往后循环

01背包、完全背包、多重背包、分组背包和混合背包

注意很多 dp[i]的定义 dp[i] i既是value又是weight

416. 分割等和子集(01背包)

给出一个总数，一些物品，问能否凑成这个总数
leetcode

698.划分为k个相等的子集
473.火柴拼正方形

一维解法

// 本质是 集合里能否出现总和为 sum / 2 的子集
var canPartition = function(nums) {
    // 本质是能否把sum/2的背包装满
    const sum = nums.reduce((pre, cur) => pre + cur, 0)
    if(sum % 2 === 1) return false
    const capacity = sum / 2
    // dp[i]: 当前容量能否被放满
    const dp = Array(capacity+1).fill(false)
    // 减的剩下0空间了，自然为true
    dp[0] = true
    for(let i = 0; i < nums.length; i++) {
        // 到当前j 的时候，前面的j还要用，所以倒序
        for(let j = capacity; j >= nums[i] ; j-- ) {
            // 不放 || 放
            dp[j] = dp[j] || dp[j-nums[i]]
        }
        // console.log(i,nums[i],dp);
    }

    return dp[capacity]
};
// true
console.log(canPartition([1,5,11,5]));

二维解法

var canPartition = function (nums) {
    const sum = nums.reduce((pre, cur) => pre + cur, 0);
    if (sum % 2 !== 0) return false;
    const capacity = sum / 2;
    const m = nums.length;
    const n = capacity;

    // dp[i][j]: 前 i 个数是否能装满容量 j
    const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(false));
    // 无物品且容量0可达
    dp[0][0] = true; 
    for (let i = 1; i <= m; i++) {
        const w = nums[i - 1];
        for (let j = 0; j <= capacity; j++) {
            if (w > j) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = dp[i - 1][j] || dp[i - 1][j - w];
        }
    }

    return dp[m][n];
};
// true
console.log(canPartition([1,5,11,5]));

1049. 最后一块石头的重量 II(01背包)

给出一个总数，一些物品，问能否凑成这个总数
leetcode

一维解法

var lastStoneWeightII = function (stones) {
    const sum = stones.reduce((pre, cur) => pre + cur, 0);
    const capacity = Math.floor(sum / 2);
    const m = stones.length;
    const n = capacity;
    const dp = Array(n + 1).fill(0);

    for (let i = 0; i < m; i++) {
        for (let j = capacity; j >= stones[i]; j--) {
            dp[j] = Math.max(dp[j], stones[i] + dp[j - stones[i]]);
        }
    }

    return Math.abs(dp[n] * 2 - sum);
};

二维解法

var lastStoneWeightII = function (stones) {
    // 这题本质是找到尽可能接近 sum/2 的组，也即 背包的 value/容量 最大 为 sum/2。
    // dp[j]: 前j项最大价值为dp[j]
    // 总容量j 减去当前j的容量，剩余的容量的价值， 加上当前j的价值；与上一次ap[j]比出最大值
    const sum = stones.reduce((pre, cur) => pre + cur, 0);
    const capacity = Math.floor(sum / 2);
    const m = stones.length;
    const n = capacity;
    // 无物品 dp[0][*] = 0; 无容量 dp[*][0] = 0
    const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
    // 因为会有 i-1,所以上面多造了一行0
    for (let i = 1; i <= m; i++) {
        const w = stones[i - 1];
        for (let j = 0; j <= capacity; j++) {
            // 如果 物品i的重量w > 容量j, 说明放不下, 直接继承(一维写法可直接跳过，自动就继承了)
            if (w > j) dp[i][j] = dp[i - 1][j];
            // 不放: dp[i-1][j]; 放: w + dp[i-1][j-w](意为 i放进去 + 放满剩下的重量)
            else dp[i][j] = Math.max(dp[i - 1][j], w + dp[i - 1][j - w]);
        }
        // console.log(i,w,dp[i]);
    }
    return Math.abs(dp[m][n] * 2 - sum);
};
// 1 2 [ 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
// 2 7 [ 0, 0, 2, 2, 2, 2, 2, 7, 7, 9, 9, 9 ]
// 3 4 [ 0, 0, 2, 2, 4, 4, 6, 7, 7, 9, 9, 11 ]
// 4 1 [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
// 5 8 [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
// 6 1 [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
// 1
console.log(lastStoneWeightII([2, 7, 4, 1, 8, 1]));

494. 目标和(01背包,组合)

给出一个总数，一些物品，问能否凑成这个总数
leetcode

一维解法

var findTargetSumWays = function (nums, target) {
    // 本质是 将数组分成两个集合，其中一个集合比另一个集合多 target
    // 转换成数学就是, 要装满下面的 大集合capacity 有多少种方法
    // 小集合 = sum - capacity ;  capacity - 小集合 = target;
    // 大集合capacity = (sum + target) / 2
    const sum = nums.reduce((pre, cur) => pre + cur, 0);
    if (Math.abs(target) > sum) return 0
    if ((target + sum) % 2 === 1) return 0;
    
    const capacity = (sum + target) / 2;
    const dp = Array(capacity + 1).fill(0);
    dp[0] = 1;
    for (let i = 0; i < nums.length; i++) {
        for (let j = capacity; j >= nums[i]; j--) {
            // 不加入 + 加入
            dp[j] = dp[j] + dp[j - nums[i]];
        }
        // console.log(i, nums[i], dp);
    }
    return dp[capacity];
};
// 0 1 [ 1, 1, 0, 0, 0 ]
// 1 1 [ 1, 2, 1, 0, 0 ]
// 2 1 [ 1, 3, 3, 1, 0 ]
// 3 1 [ 1, 4, 6, 4, 1 ]
// 4 1 [ 1, 5, 10, 10, 5 ]
// console.log(findTargetSumWays([1, 1, 1, 1, 1], 3));

474. 一和零

leetcode

var findMaxForm = function (strings, m, n) {
    // 【两个维度的容量】 的计算过程需要记录
    // dp[m][n] 满足m n的最大子集长度，初始为0
    const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

    for (const str of strings) {
        let zero = (one = 0);
        for (let c of str) {
            if (c === '0') zero++;
            else one++;
        }
        // 倒序: 这题本质是以前的一维滚动数组，要复上一轮str数据，每轮刷整个二维数组
        for (let i = m; i >= zero; i--) {
            for (let j = n; j >= one; j--) {
                // 不放 放
                dp[i][j] = Math.max( dp[i][j], dp[i - zero][j - one] + 1 );
            }
        }
    }
    return dp[m][n]
};

为什么滚动数组需要倒叙遍历？

因为滚动数组复用需要i-1轮遍历的结果，

假设从后往前做遍历，我们在做第i轮循环的时候，先计算容量j 较大的数据，此数据会依赖 i-1 轮的遍历结果

前面还依旧保留者 i-1次遍历的dp数据，以供第i轮使用。

假设从前往后做遍历，可以预见容量j 较小的dp数据会先被覆盖成为第i轮的数据，使得容量j较大的数据无法复用 i-1轮的结果，

或者说这样遍历，导致每轮i种，每个容量j 都基于了新的当前i去计算(视为有无数个i物品，也即完全背包问题)

以01背包的思路甚至可以认为，这样从前往后遍历，已经不仅仅有i层，而是 i*j 层。因为每个 j-1 其实都已经被覆盖为了第j层的数据

完全背包

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

01背包:当前物品放或不放，完全背包:当前物品放无数个

所以我们每次基于前面已经考虑过当前i物品存在情况的dp[i]进行推导，

而非上一列未考虑当前i物品存在的dp[i-1]

所以 01背包和完全背包在一维dp算法上有区别, 遍历顺序

01背包从大到小遍历(复用i-1的数据)，完全背包从小到大遍历(复用物品i已存在的数据)

518. 零钱兑换 II

leetcode

var change = function (amount, coins) {
    const dp = Array(amount + 1).fill(0);
    dp[0] = 1;
    for (let i = 0; i < coins.length; i++) {
        for (let j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount]
};

这题是求【多少种摆法】而不是求【能装满背包的最大价值】
因此外层内层循环不能互换(纯完全背包求价值，可以互换)
同时因为是求凑成总和的组合数，所以这题要的是组合，必须外物体内容量

完全背包的排列和组合

组合: 外层遍历物体，内层遍历容量 物品顺序固定，不存在重复

for (int i = 0; i < coins.size(); i++) { // 先固定“使用哪些物品”
    for (int j = coins[i]; j <= amount; j++) { // 再考虑“凑成 j 的方式”
        dp[j] += dp[j - coins[i]];
    }
}

//  5 [1,2,5]
0 1 [ 1, 1, 1, 1, 1, 1 ]
1 2 [ 1, 1, 2, 2, 3, 3 ]
2 5 [ 1, 1, 2, 2, 3, 4 ]

排列: 外层遍历容量，内层遍历物体 对每个容量，末尾放入物体

var change = function (amount, coins) {
    const dp = Array(amount + 1).fill(0)
    dp[0] = 1
    for (let j = 1; j <= amount; j++) { // 遍历容量
        for (let i = 0; i < coins.length; i++) { // 遍历物品
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount]
};

//  5 [1,2,5]
//  0  1  2  3  4  5
0 [ 1, 0, 0, 0, 0, 0 ]
1 [ 1, 1, 0, 0, 0, 0 ]
2 [ 1, 1, 2, 0, 0, 0 ]
3 [ 1, 1, 2, 3, 0, 0 ]
4 [ 1, 1, 2, 3, 5, 0 ]
5 [ 1, 1, 2, 3, 5, 9 ]

针对每一个容量，放入 1 2 5，
例如: dp[4] 时,
i = 1(末尾放入1,剩下3), dp[4] = dp[4] + dp[3] = 0 + 3 = 3
i = 2(末尾放入2,剩下2), dp[4] = dp[4] + dp[2] = 3 + 2 = 5
i = 5(末尾放入5), 跳过
dp[4] 共计有 3 + 2 种排列方式

抽象理解:
dp[j] = dp[j] + dp[j - coins[i]] 代表末尾放入当前i，剩余容量再找dp
一轮内层物体i遍历完之后，dp[j] 就是这些摆法之和
每轮算好dp数组一个数，
所有数在当前容量末尾的情况都遍历到了，排列

外物体内容量的 dp打印总是数据修改均匀分布
外容量内物体的 dp打印总是数据在左下三角，右上全是0
因为横纵坐标都是容量每轮确定一个容量的结果

377. 组合总和 Ⅳ

leetcode

var combinationSum4 = function(nums, target) {
    // 很简单容量为4，nums种找元素装满target，但强调顺序
    // dp[i] 装满dp[i] 有几种方法
    const dp = Array(target + 1).fill(0)
    // 初始化容量为0 有1种摆法(j-nums[i]=0物体恰好适配容量，应+1)
    dp[0] = 1
    for(let j = 1; j <= target; j++) {
        // 区分顺序，针对每个容量，遍历item
        for(let i = 0; i < nums.length; i++) {
            if(j < nums[i]) continue;
            dp[j] += dp[j - nums[i]]
        }
        // console.log(j,dp);
    }

    return dp[target]
};
// 1 [ 1, 1, 0, 0, 0 ]
// 2 [ 1, 1, 2, 0, 0 ]
// 3 [ 1, 1, 2, 4, 0 ]
// 4 [ 1, 1, 2, 4, 7 ]
// 7
console.log(combinationSum4([1,2,3],4));

70. 爬楼梯(每次任意级台阶)

leetcode

题目修改为每次可走任意级台阶m

var climbStairs = function(n, m) {
    const dp = Array(n+1).fill(0)
    dp[0] = 1
    for(let j = 1; j <= n; j++) {
        for(let i = 1; i <= m && i <= j; i++ ) {
            dp[j] += dp[j-i]
        }
    }
    return dp[n]
}

容量为n 元素为1-m, 到n共有多少种排列
dp[j]: 装满容量j共有 dp[j] 种排列
&& i <= j 代替了 if(j < nums[i]) 因为这里i与物体大小一一对应，可以这样写

322. 零钱兑换

leetcode

var coinChange = function (coins, amount) {
    // 背包容量amount，元素coins，最少元素满足amount
    // 这题内外循环都行
    const dp = Array(amount + 1).fill(Infinity);
    // `j-coins[i]=0`剩余容量0，要补的钱数也0
    dp[0] = 0;
    for (let i = 0; i < coins.length; i++) {
        for (let j = coins[i]; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
        }
        // console.log(i,coins[i],dp)
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
};
// 0 1 [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
// 1 2 [ 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5,  6  ]
// 2 5 [ 0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2,  3  ]
// 3
// console.log(coinChange([1,2,5], 11));

279. 完全平方数

leetcode

var numSquares = function(n) {
    // 前一选择影响后一步的选择容量等于价值
    // 是组合，外层遍历 物品i
    // 是完全背包，内层正序遍历 容量j
    // dp[i]: 和为i的最少完全平方数的数量
    // dp[i] = Math.min(dp[i], dp[j - Math.pow(i,2)])
    const dp = Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i * i <= n; i++) {
        for (let j = i * i; j <= n; j++) {
            // 不选 选
            dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
        }
    }
    return dp[n]
};

139. 单词拆分

leetcode

// 针对每个容量，用物体一个个匹配 【排序】 【完全背包】
var wordBreak = function (s, wordDict) {
    const dp = Array(s.length + 1).fill(false);
    // 裁剪剩下的 s = '' 必然true
    dp[0] = true;
    // 
    for (let j = 1; j <= s.length; j++) {
        for (let i = 0; i < wordDict.length; i++) {
            const l = wordDict[i].length;
            if (j < l) continue;
            // 前面有匹配上 || 当前匹配上
            dp[j] = dp[j] || (wordDict[i] === s.slice(j - l, j) && dp[j - l]);
            // console.log(j, wordDict[i], s.slice(j - l, j), dp);
        }
    }
    return dp[s.length];
};
// console.log(wordBreak('leetcode', ['leet', 'code']));

多重背包

多重背包就是完全背包但数量有限，其按数量摊开可视为01背包

解法为在01背包的基础上再加一层循环，针对每个物品i的数量进行循环

function testMultiPack() {
    const bagSize = 10;
    const weightArr = [1, 3, 4], valueArr = [15, 20, 30], amountArr = [2, 3, 2];
    const goodsNum = weightArr.length;
    const dp = new Array(bagSize + 1).fill(0);
    // 遍历物品
    for (let i = 0; i < goodsNum; i++) {
        // 遍历物品个数，j=0放第一个，j=amountArr[i]-1放最后一个
        for (let j = 0; j < amountArr[i]; j++) {
            // 遍历背包容量
            for (let k = bagSize; k >= weightArr[i]; k--) {
                dp[k] = Math.max(dp[k], dp[k - weightArr[i]] + valueArr[i]);
            }
            console.log(i,j,valueArr[i],dp);
        }
    }
}
testMultiPack();

0 0 15 [ 0, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15 ]
0 1 15 [ 0, 15, 30, 30, 30, 30, 30, 30, 30, 30, 30 ]
1 0 20 [ 0, 15, 30, 30, 35, 50, 50, 50, 50, 50, 50 ]
1 1 20 [ 0, 15, 30, 30, 35, 50, 50, 55, 70, 70, 70 ]
1 2 20 [ 0, 15, 30, 30, 35, 50, 50, 55, 70, 70, 75 ]
2 0 30 [ 0, 15, 30, 30, 35, 50, 60, 60, 70, 80, 80 ]
2 1 30 [ 0, 15, 30, 30, 35, 50, 60, 60, 70, 80, 90 ]

代码随想录递推公式总结篇

[leetcode](https://programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html#%E8%83%8C%E5%8C%85%E9%80%92%E6%8E%A8%E5%85%AC%E5%BC%8F>

198.打家劫舍

leetcode

var rob = function(nums) {
    // dp[i] 前i项 偷与不偷 能获取的钱的大值
    // dp[0] 只有1个房屋自然 = nums[0], dp[1] 自然是max两个房屋
    const dp = [nums[0], Math.max(nums[0], nums[1])];
    for (let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[nums.length - 1];
};
// [ 2, 7, 11, 11, 12 ]
rob([ 2, 7,  9,  3,  1 ])

通用解法

var rob = function (nums) {
    const l = nums.length;
    // dp[i][0]: 不偷i前i项最多能拿的钱, dp[i][1]: 偷i前i项最多能拿的钱
    const dp = Array(l + 1).fill(0).map(() => Array(2).fill(0));
    // 表示逐渐增加的房子: 不偷 偷
    for (let i = 1; i <= l; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = nums[i - 1] + dp[i - 1][0];
    }
    return Math.max(dp[l][0], dp[l][1]);
};
// console.log(rob([2,7,9,3,1])); // 12

213.打家劫舍II

leetcode

类似循环的题目都可以首/尾各做一次再手动比较一次的做法

var rob = function (nums) {
    // 多了一层选首不能选尾，选尾不能选首，也即多一个max
    if (nums.length === 1) return nums[0]
    const front = robRange(nums, 0, nums.length - 2)
    const end = robRange(nums, 1, nums.length - 1)
    return Math.max(front, end)
};

// s -> startIndex  e -> endIndex
const robRange = (nums, s, e) => {
    if (s === e) return nums[s]
    // 这里必须nums.length创建array，因为dp得和nums的i对应上
    const dp = Array(nums.length).fill(0)
    dp[s] = nums[s]
    dp[s + 1] = Math.max(nums[s], nums[s + 1])
    for (let i = s + 2; i <= e; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
    }
    // console.log(dp);
    return dp[e]
}
rob([ 2, 3, 2 ])
[ 2, 3, 0 ]
[ 0, 3, 3 ]

337. 打家劫舍 III

leetcode

const rob = root => {
    // 后序遍历函数
    const postOrder = node => {
        // 递归出口
        if (!node) return [0, 0];
        // 遍历左子树
        const left = postOrder(node.left);
        // 遍历右子树
        const right = postOrder(node.right);
        // 不偷当前节点，左右子节点都可以偷或不偷，取最大值
        const DoNot = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // 偷当前节点，左右子节点只能不偷
        const Do = node.val + left[0] + right[0];
        // [不偷，偷]
        return [DoNot, Do];
    };
    const res = postOrder(root);
    // 返回最大值
    return Math.max(...res);
};

买卖股票

为什么股票问题 必须显式设定两种或以上状态, 而背包问题不需要?

背包问题不需要记录前一次状态, i选择效果只依赖于剩余容量, 只需记录容量唯一维度

买卖股票本质上是一个有后效性的问题, i选择效果依赖于 i-1的 历史路径

我们通过设定多个维度的状态记录器, 将其变为无后效性问题

假设简单设定 dp[i]表示前i天最大利润, 则无法模拟买入卖出的互斥关系

可简化: 由于买卖股票只依赖于i-1, 只需要够记录上一层状态变量, 而不使用dp数组

198.打家劫舍同理！

121.买卖股票的最佳时机

leetcode

var maxProfit = function (prices) {
    const l = prices.length;
    // 只能买卖一次，假设昨天是卖出的状态，那今天再买入就只有-prices[i],
    const dp = Array(l).fill(0).map(() => Array(2).fill(0));
    dp[0] = [-prices[0], 0];
    for (let i = 1; i < prices.length; i++) {
        // 持有: 昨天持有 昨天不持有
        dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
        // 不持有: 昨天不持有 昨天持有
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
    }
    return dp[l - 1][1];
};
// [[0, -7], [0, -1], [4, -1], [4, -1], [5, -1], [5, -1]]
console.log(maxProfit([7, 1, 5, 3, 6, 4]));

只能买卖一次，今天买入的代价恒为 -prices[i], 不由 dp[i-1][0]转移而来

var maxProfit = function (prices) {
    let toDo = -prices[0]
    let noDo = 0
    for(let i = 1; i < prices.length; i++) {
        noDo = Math.max(noDo, toDo + prices[i])
        toDo = Math.max(toDo, -prices[i])
    }
    return noDo
};

动态规划解决的问题都是 重叠子问题 无后效性的问题

解题本质是 递归思想 + 记忆化搜索工具 + 递推实现

通过状态定义(保留求解所需的最小信息) 消除后效性, 转变成小问题, 得到递推

区分于贪心, 贪心没有状态推导, 而是从局部直接选最优的

var maxProfit = function(prices) {
    let lowerPrice = prices[0];// 重点是维护这个最小值（贪心的思想） 
    let profit = 0;
    for(let i = 0; i < prices.length; i++){
        lowerPrice = Math.min(lowerPrice, prices[i]);// 贪心地选择左面的最小价格
        profit = Math.max(profit, prices[i] - lowerPrice);// 遍历一趟就可以获得最大利润
    }
    return profit;
};

122. 买卖股票的最佳时机 II

leetcode

// dp[i] 前i天能获取的最大利润
var maxProfit = function(prices) {
    const l = prices.length;
    const dp = Array(l).fill(0).map(() => [0,0]);
    dp[0][0] = -prices[0]
    for(let i = 1; i < l; 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[l-1][1]
};

var maxProfit = function (prices) {
    let toDo = -prices[0]
    let noDo = 0
    for(let i = 1; i < prices.length; i++) {
        // const preNoDo = noDo
        // const preToDo = toDo
        noDo = Math.max(noDo, toDo + prices[i])
        toDo = Math.max(toDo, noDo - prices[i])
    }
    return noDo
};

console.log(maxProfit([7, 1, 5, 3, 6, 4]))

noDo 已经更新, 却还能直接用于计算 toDo, 因为这题当天能卖能买, 巧合成功

309（含冷冻期）或 714（含手续费）等情形中, 就不能这样写

123. 买卖股票的最佳时机 III

leetcode

var maxProfit = function(prices) {
    const l = prices.length;
    const dp = Array(l).fill(0).map(() => [0,0,0,0]);
    // 第一次持有
    dp[0][0] = -prices[0]; 
    // 第二次持有(第一次当天买当天卖,再第二次持有)
    dp[0][2] = -prices[0];  

    for (let i = 1; i < l; i++) {
        // 第一次持有
        dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
        // 第一次不持有
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
        // 第二次持有（依赖第一次不持有）
        dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] - prices[i]);
        // 第二次不持有（依赖第二次买入）
        dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i]);
    }

    return dp[l-1][3];
};
// maxProfit([2,1,4,5,2,9,7])

第一次卖出和第二次卖出，不需要特意切换，前期第一次第二次就是在同线执行。

只需要一次买卖的情况，dp[l-1][4] 和 dp[l-1][2] 是相等的。

但如果是需要两次买卖的情况，一定是 dp[l-1][4] 大

const maxProfit = prices => {
    const len = prices.length;
    const dp = new Array(5).fill(0);
    dp[1] = -prices[0];
    dp[3] = -prices[0];
    for (let i = 1; i < len; i++) {
        dp[1] = Math.max(dp[1], dp[0] - prices[i]);
        dp[2] = Math.max(dp[2], dp[1] + prices[i]);
        dp[3] = Math.max(dp[3], dp[2] - prices[i]);
        dp[4] = Math.max(dp[4], dp[3] + prices[i]);
    }
    return dp[4];
};

188. 买卖股票的最佳时机 IV

leetcode

var maxProfit = function (k, prices) {
    // 题目要求 可以做k次买卖，同一时间只能做一笔
    // 但模拟中其实是同时在做，但如果有多笔，后续会计入前面的收益
    // 其实在每轮i中，后几次的买卖都会立刻在当轮计入前面的收益
    const l = prices.length;
    const status = 2 * k + 1;
    const arr = Array(status).fill(0);
    // 初始化所有买入
    for (let k = 1; k < status; k += 2) arr[k] = -prices[0];
    for (let i = 1; i < l; i++) {
        // 遍历推导状态: 奇数是买入 偶数是卖出
        // 从1开始, 0是用来便于推导的, 不参与状态
        for (let j = 1; j < status; j++) {
            const noOrDo = j % 2 === 1
                ? arr[j - 1] - prices[i] : arr[j - 1] + prices[i];
            arr[j] = Math.max(arr[j], noOrDo);
        }
    }
    return arr[status - 1];
};
maxProfit([3, 2, 6, 5, 0, 3])

309. 买卖股票的最佳时机含冷冻期

leetcode

// 每天的状态有 可买入 
var maxProfit = function (prices) {
    const l = prices.length
    const dp = new Array(l).fill(0).map(() => new Array(4).fill(0))
    dp[0][0] = -prices[0] // 持有
    // 0持有 = 前一天是， 持有 或 当天买入(保持不持有) 或 当天买入(冷静期)
    // 1保持不持有(可随时买入) = 前一天是， 保持不持有 或 冷静期
    // 2当天卖出(触发冷静期) = 前一天是， 持有
    // 3冷静期(无法买入) = 前一天是， 当天卖出
    // 23用于精确跟踪 `卖出` 和 `冷静期`
    // 合并13, 无法区分是否可买入(冷静期)
    // 合并23, 无法暂停一天, 3依赖前一天2的数据, 以此实现暂停一天
    for (let i = 1; i < l; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][3]) - prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3])
        dp[i][2] = dp[i - 1][0] + prices[i]
        dp[i][3] = dp[i - 1][2]
    }
    return Math.max(dp[l - 1][1], dp[l - 1][2], dp[l - 1][3])
};

714. 买卖股票的最佳时机含手续费

leetcode

var maxProfit = function (prices, fee) {
    let hold = -prices[0] - fee
    let not = 0
    for (let i = 1; i < prices.length; i++) {
        hold = Math.max(hold, not - prices[i] - fee)
        not = Math.max(not, hold + prices[i])
    }
    return not
};

var maxProfit = function (prices, fee) {
    const l = prices.length
    const dp = new Array(l).fill(0).map(() => new Array(2).fill(0))

    dp[0][0] = 0
    dp[0][1] = -prices[0] - fee
    for (let i = 1; i < l; 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] - fee)
    }

    return dp[l - 1][0]
};

子序列问题

300. 最长递增子序列

leetcode

const lengthOfLIS = (nums) => {
    // dp[i] 以dp[i]结尾 的最长严格递增子序列长度
    // dp[i] = 前i-1中 满足尾数小于当前数 num[j] < num[i] 中的最大值+1
    // 初始化1,且i从1开始,因为dp[0]肯定是1,且后续数很小的话也会是1
    let dp = Array(nums.length).fill(1);
    let result = 1;
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        result = Math.max(result, dp[i]);
    }
    return result;
};
// [ 1, 2, 3, 4, 5, 3, 6, 4, 5 ]
lengthOfLIS([1, 3, 6, 7, 9, 4, 10, 5, 6])

674. 最长连续递增序列

leetcode

1var findLengthOfLCIS = function (nums) {
    // 要求连续，那就是以i-1为基础计算i
    let pre = 1, max = 0
    for (let i = 1; i < nums.length; i++) {
        const cur = nums[i - 1] < nums[i] ? pre + 1 : 1
        max = Math.max(max, cur)
        pre = cur
    }
    return max
};

718. 最长重复子数组

leetcode

const findLength = (nums1, nums2) => {
    const [m, n] = [nums1.length, nums2.length];
    const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
    let res = 0;
    // 用二维数组记录所有比较情况
    // dp[i][j] 以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共连续子序列的长度
    // 递推公式需要用到i-1，所以要初始化0位置，并从1位置开始
    for (let i = 1; i <= m; i++) {
        // 每放入一个nums1[i],遍历nums2[j],找有没有跟自己相等的,有就是当前dp+1
        for (let j = 1; j <= n; j++) {
            if (nums1[i - 1] === nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            res = Math.max(res, dp[i][j])
        }
    }
    return res;
};

const findLength2 = (nums1, nums2) => {
    const [m, n] = [nums1.length, nums2.length];
    const dp = Array(n + 1).fill(0)
    let res = 0;
    // 由于每次都只需要用到i-1层，可使用滚动数组
    // 由于需要用到前面的值，需要内层倒序
    for(let i = 1; i <= m; i++) {
        for(let j = n; j > 0; j--) {
            dp[j] = nums1[i-1] === nums2[j-1] ? dp[j-1]+1 : 0
            res = Math.max(res, dp[j])
        }
    }
    return res
};

findLength2([1, 2, 3, 2, 1], [3, 2, 1, 4, 7])

       3, 2, 1, 4, 7
  [ 0, 0, 0, 1, 0, 0 ]
1 [ 0, 0, 0, 1, 0, 0 ]
2 [ 0, 0, 1, 0, 0, 0 ]
3 [ 0, 1, 0, 0, 0, 0 ]
2 [ 0, 0, 2, 0, 0, 0 ]
1 [ 0, 0, 0, 3, 0, 0 ]

1143. 最长公共子序列

leetcode

var longestCommonSubsequence = function (text1, text2) {
    // dp[i][j] text1中的前i 和 text2中的前j 的公共子序列最长长度
    const [m, n] = [text1.length, text2.length];
    const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // dp[i - 1][j - 1]:除这两个外的最长长度 + 1:这两个相等
            // 如果不相等, i-1: 丢掉当前i, j-1: 丢掉当前j
            dp[i][j] = text1[i - 1] === text2[j - 1]
                ? dp[i - 1][j - 1] + 1
                : Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
};
// 一维DP
var longestCommonSubsequence = function (text1, text2) {
    // dp[i][j] text1中的前i 和 text2中的前j 的公共子序列最长长度
    const n = text2.length;
    const dp = new Array(n + 1).fill(0);

    for (let i = 1; i <= text1.length; i++) {
        let pre = 0; // 后续对应 dp[i-1][j-1]
        // 倒序虽然能避免覆盖前值, 轻松拿到dp[i-1][j-1]
        // 但 dp[i][j-1] 代表当前轮i, 必须正序遍历才能拿到,即dp[j - 1]
        for (let j = 1; j <= n; j++) {
            const tmp = dp[j]; // 下一轮的 dp[i-1][j-1]
            // 一维中不论正序倒序, dp[i-1][j]就是dp[j]本身
            dp[j] = text1[i - 1] === text2[j - 1]
                ? pre + 1
                : Math.max(dp[j], dp[j - 1]);
            pre = tmp;
        }
    }
    return dp[n];
};
// longestCommonSubsequence("abcde","ace")
// [
//        a  c  e
//   [ 0, 0, 0, 0 ],
// a [ 0, 1, 1, 1 ],
// b [ 0, 1, 1, 1 ],
// c [ 0, 1, 2, 2 ],
// d [ 0, 1, 2, 2 ],
// e [ 0, 1, 2, 3 ]
// ]

对比点	718. 最长重复子数组	1143. 最长公共子序列
题目关键词	subArray / 子数组	subSequence / 子序列
是否连续	✅ 必须连续	❌ 不要求连续
状态定义	以 nums1[i-1], nums2[j-1] 结尾的连续公共子数组长度	前 i、前 j 个字符的公共子序列长度
相等时	`dp[i][j] = dp[i-1][j-1] + 1`	`dp[i][j] = dp[i-1][j-1] + 1`
不相等时	`dp[i][j] = 0`（断了连续性）	`dp[i][j] = max(dp[i-1][j], dp[i][j-1])`（可跳过）
结果	所有 `dp[i][j]` 中的最大值	`dp[m][n]`
图形延伸方向	仅沿 ↖️ 对角线延伸（连续）	三方向（⬆️、⬅️、↖️）取最大

1035.不相交的线

leetcode

var maxUncrossedLines = function (nums1, nums2) {
    // dp[i][j] 前ij项能连最多的线
    const [m, n] = [nums1.length, nums2.length];
    const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 相等时必然比去掉一个的情况更大
            dp[i][j] = nums1[i-1] === nums2[j-1]
                ? dp[i - 1][j - 1] + 1
                : Math.max( dp[i - 1][j], dp[i][j - 1])
        }
        // console.log(i,nums1[i-1],dp[i]);
    }
    return dp[m][n]
};
// 一维DP
var maxUncrossedLines = function (nums1, nums2) {
    const n = nums2.length;
    const dp = new Array(n + 1).fill(0);

    for (let i = 1; i <= nums1.length; i++) {
        let pre = dp[0]; // 对应 dp[i-1][j-1]
        for (let j = 1; j <= n; j++) {
            const tmp = dp[j];
            dp[j] = nums1[i - 1] === nums2[j - 1]
                ? pre + 1
                : Math.max(dp[j], dp[j - 1]);
            pre = tmp;
        }
    }
    return dp[n];
};
// 3
// console.log(maxUncrossedLines([2,5,1,2,5],[10,5,2,1,5,2]));

53. 最大子数组和

leetcode

// 1维动态规划
var maxSubArray = function (nums) {
    // dp[i] 以nums[i]结尾的最大连续子数组和
    const dp = Array(nums.length + 1).fill(0);
    let result = -Infinity;
    for (let i = 1; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i - 1], nums[i - 1]);
        result = Math.max(result, dp[i]);
    }
    return result;
};
// 0维动态规划
const maxSubArray = (nums) => {
    let sum = 0, result = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        sum = Math.max(sum + nums[i], nums[i]);
        result = Math.max(result, sum);
    }
    return result;
};
// 贪心 其实就是 0维
var maxSubArray = function(nums) {
    let [sum, result] = [0, -Infinity]
    for(let i = 0; i < nums.length; i++) {
        sum < 0 && (sum = 0)
        sum += nums[i]
        sum > result && (result = sum)
    }
    return result
};

✅dp[i] 以 i 项结尾的最大子数组和
❌dp[i] 前 i 项的最大子数组和定义2中无法确定对应子数组是否连续
i代表的子数组可能不含i项,而i+1项最大值可能要保证前面连续

392.判断子序列

leetcode

var isSubsequence = function (s, t) {
    // dp[i][j]: 前s[i]项 前t[j]项 相同子序列长度
    // 相等, 则看除了这两个数, 前面的数是否找到, 上一轮且小于当前j
    // 不相等, 则继承i轮j前面的(前面找到了就行)
    const [m, n] = [s.length, t.length];
    const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++)
        for (let j = 1; j <= n; j++)
            dp[i][j] = s[i - 1] === t[j - 1]
                ? dp[i - 1][j - 1] + 1
                : dp[i][j - 1];
    return dp[m][n] === m;
};
// 一维DP
var isSubsequence = function (s, t) {
    const [m, n] = [s.length, t.length];
    const dp = Array(n + 1).fill(0);

    for (let i = 1; i <= m; i++) {
        let pre = dp[0]; // 对应 dp[i-1][j-1]
        for(let j = 1; j <= n; j++) {
            const tmp = dp[j];
            dp[j] = s[i - 1] === t[j - 1]
                ? pre + 1
                : dp[j - 1];
            pre = tmp
        }
    }
    return dp[n] === m;
};
// [
//     [0, 0, 0, 0, 0, 0, 0],
//     a[0, 1, 1, 1, 1, 1, 1],
//     b[0, 0, 0, 2, 2, 2, 2],
//     c[0, 0, 0, 0, 0, 0, 3]
// ]
// isSubsequence("abc", "ahbgdc")

// 其实只要按顺序能在t中找到所有s就行，遍历s，在t中按顺序找
var isSubsequence = function(s, t) {
    let i = j = 0
    for(; j < t.length; j++) s[i] === t[j] && i++
    return i === s.length
};

115.不同的子序列

var numDistinct = function (s, t) {
    // dp[i][j]: s[i]中出现了多少次t[j]
    const [m,n] = [s.length,t.length]
    const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0))

    // s中找 t长度为0，初始化为1
    for (let i = 0; i <= m; i++)dp[i][0] = 1;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s[i - 1] === t[j - 1]) {
                // 相等时, 不用s[i-1]  +  用s[i-1]
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
            } else {
                // 不相等, 只能不用s[i-1]
                dp[i][j] = dp[i - 1][j]
            }
        }
    }
    return dp[m][n]
};
console.log(numDistinct('rabbbit', 'rabbit'));
[
          r, a, b, b, i, t 
     [ 1, 0, 0, 0, 0, 0, 0 ],
    r[ 1, 1, 0, 0, 0, 0, 0 ],
    a[ 1, 1, 1, 0, 0, 0, 0 ],
    b[ 1, 1, 1, 1, 0, 0, 0 ],
    b[ 1, 1, 1, 2, 1, 0, 0 ],
    b[ 1, 1, 1, 3, 3, 0, 0 ],
    i[ 1, 1, 1, 3, 3, 3, 0 ],
    t[ 1, 1, 1, 3, 3, 3, 3 ]
]

动态规划#

技巧#

基础问题#

509. 斐波那契数#

70. 爬楼梯#

746. 使用最小花费爬楼梯#

62. 不同路径#

63. 不同路径 II#

343. 整数拆分#

背包问题#

416. 分割等和子集(01背包)#

1049. 最后一块石头的重量 II(01背包)#

494. 目标和(01背包,组合)#

474. 一和零#

为什么滚动数组需要倒叙遍历？#

完全背包#

518. 零钱兑换 II#

完全背包的排列和组合#

377. 组合总和 Ⅳ#

70. 爬楼梯(每次任意级台阶)#

322. 零钱兑换#

279. 完全平方数#

139. 单词拆分#

多重背包#

代码随想录递推公式总结篇#

198.打家劫舍#

213.打家劫舍II#

337. 打家劫舍 III#

买卖股票#

121.买卖股票的最佳时机#

122. 买卖股票的最佳时机 II#

123. 买卖股票的最佳时机 III#

188. 买卖股票的最佳时机 IV#

309. 买卖股票的最佳时机含冷冻期#

714. 买卖股票的最佳时机含手续费#

子序列问题#

300. 最长递增子序列#

674. 最长连续递增序列#

718. 最长重复子数组#

1143. 最长公共子序列#

1035.不相交的线#

53. 最大子数组和#

392.判断子序列#

115.不同的子序列#

583. 两个字符串的删除操作#

72. 编辑距离#

647. 回文子串#

516.最长回文子序列#

动态规划

技巧

基础问题

509. 斐波那契数

70. 爬楼梯

746. 使用最小花费爬楼梯

62. 不同路径

63. 不同路径 II

343. 整数拆分

背包问题

416. 分割等和子集(01背包)

1049. 最后一块石头的重量 II(01背包)

494. 目标和(01背包,组合)

474. 一和零

为什么滚动数组需要倒叙遍历？

完全背包

518. 零钱兑换 II

完全背包的排列和组合

377. 组合总和 Ⅳ

70. 爬楼梯(每次任意级台阶)

322. 零钱兑换

279. 完全平方数

139. 单词拆分

多重背包

代码随想录递推公式总结篇

198.打家劫舍

213.打家劫舍II

337. 打家劫舍 III

买卖股票

121.买卖股票的最佳时机

122. 买卖股票的最佳时机 II

123. 买卖股票的最佳时机 III

188. 买卖股票的最佳时机 IV

309. 买卖股票的最佳时机含冷冻期

714. 买卖股票的最佳时机含手续费

子序列问题

300. 最长递增子序列

674. 最长连续递增序列

718. 最长重复子数组

1143. 最长公共子序列

1035.不相交的线

53. 最大子数组和

392.判断子序列

115.不同的子序列

583. 两个字符串的删除操作

72. 编辑距离

647. 回文子串

516.最长回文子序列