关于leetcode:用javascript分类刷leetcode3动态规划图文视频讲解

什么是动静布局

动静布局，英文：Dynamic Programming，简称 DP，将问题合成为互 相重叠的子问题，通过重复求解子问题来解决原问题就是动静布局，如果某一问题有很多重叠子问题，应用动静布局来解是比拟无效的。

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

动静布局和其余算法的区别

1. 动静布局和分治的区别：动静布局和分治都有最优子结构，然而分治的子问题不重叠
2. 动静布局和贪婪的区别：动静布局中每一个状态肯定是由上一个状态推导进去的，这一点就辨别于贪婪，贪婪没有状态推导，而是从部分间接选最优解，所以它永远是部分最优，然而全局的解不肯定是最优的。
3. 动静布局和递归的区别：递归和回溯可能存在十分多的反复计算，动静布局能够用递归加记忆化的形式缩小不必要的反复计算

动静布局的解题办法

• 递归 + 记忆化(自顶向下)
• 动静布局（自底向上）

解动静布局题目的步骤

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

斐波那契的动静布局的解题思路

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-f0YqY2hz-1678842912336)(null)]

动画过大，点击查看

暴力递归

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

70. 爬楼梯（medium）

假如你正在爬楼梯。须要 n 阶你能力达到楼顶。

每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？

示例 1：

输出：n = 2
输入：2
解释：有两种办法能够爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输出：n = 3
输入：3
解释：有三种办法能够爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提醒：

1 <= n <= 45

办法 1. 动静布局

• 思路：因为每次能够爬 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;
}

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 7
4 1 8 3
自顶向下的最小门路和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：

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

提醒：

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i – 1].length + 1
-104 <= trianglei <= 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];
};

312. 戳气球 (hard)

有 n 个气球，编号为 0 到 n – 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

当初要求你戳破所有的气球。戳破第 i 个气球，你能够取得 nums[i – 1] nums[i] nums[i + 1] 枚硬币。这里的 i – 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i – 1 或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能取得硬币的最大数量。

示例 1：
输出：nums = [3,1,5,8]
输入：167
解释：
nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []
coins = 315 + 358 + 138 + 181 = 167
示例 2：

输出：nums = [1,5]
输入：10

提醒：

n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100

办法 1: 动静布局

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-bt4mHgI2-1678842912740)(null)]

• 思路：dp[i][j] 示意开区间 (i,j) 能拿到的的金币，k 是这个区间 最初一个 被戳爆的气球，枚举i 和j，遍历所有区间，i-j能取得的最大数量的金币等于 戳破以后的气球取得的金钱加上之前 i-k、k-j 区间中曾经取得的金币
• 复杂度：工夫复杂度O(n^3)，n 是气球的数量，三层遍历。空间复杂度O(n^2)，dp 数组的空间。

js：

var maxCoins = function (nums) {
    const n = nums.length;
    let points = [1, ...nums, 1]; // 两边增加虚构气球
    const dp = Array.from(Array(n + 2), () => Array(n + 2).fill(0)); //dp 数组初始化
    // 自底向上转移状态
    for (let i = n; i >= 0; i--) {
        // i 一直减小
        for (let j = i + 1; j < n + 2; j++) {
            // j 不断扩大
            for (let k = i + 1; k < j; k++) {
                // 枚举 k 在 i 和 j 中的所有可能
                //i- j 能取得的最大数量的金币等于 戳破以后的气球取得的金钱加上之前 i -k,k- j 区间中曾经取得的金币
                dp[i][j] = Math.max(
                    // 挑战最大值
                    dp[i][j],
                    dp[i][k] + dp[k][j] + points[j] * points[k] * points[i]
                );
            }
        }
    }
    return dp[0][n + 1];
};

63. 不同门路 II（medium）

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

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

当初思考网格中有障碍物。那么从左上角到右下角将会有多少条不同的门路？

网格中的障碍物和空地位别离用 1 和 0 来示意。

示例 1：

输出：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输入：2
解释：3×3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的门路：

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

示例 2：

输出：obstacleGrid = [[0,1],[0,0]]
输入：1

提醒：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGridi 为 0 或 1

办法 1. 动静布局

• 思路：和 62 题一样，区别就是遇到阻碍间接返回 0
• 复杂度：工夫复杂度O(mn)，空间复杂度O(mn)，状态压缩之后是 o(n)

Js:

var uniquePathsWithObstacles = function (obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = Array(m)
        .fill()
        .map((item) => Array(n).fill(0)); // 初始 dp 数组

    for (let i = 0; i < m && obstacleGrid[i][0] === 0; ++i) {
        // 初始列
        dp[i][0] = 1;
    }

    for (let i = 0; i < n && obstacleGrid[0][i] === 0; ++i) {
        // 初始行
        dp[0][i] = 1;
    }

    for (let i = 1; i < m; ++i) {for (let j = 1; j < n; ++j) {
            // 遇到阻碍间接返回 0
            dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
};

// 状态压缩
var uniquePathsWithObstacles = function (obstacleGrid) {
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;
    let dp = Array(n).fill(0); // 用 0 填充，因为当初有障碍物，以后 dp 数组元素的值还和 obstacleGrid[i][j]无关
    dp[0] = 1; // 第一列 临时用 1 填充
    for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (obstacleGrid[i][j] == 1) {// 留神条件，遇到障碍物 dp[j]就变成 0，这里蕴含了第一列的状况
                dp[j] = 0;
            } else if (j > 0) {
                // 只有当 j >0 不是第一列了能力取到 j - 1
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
};

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 <= 20
1 <= p.length <= 30
s 只蕴含从 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 串
};

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

64. 最小门路和 (medium)

给定一个蕴含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的门路，使得门路上的数字总和为最小。

阐明：每次只能向下或者向右挪动一步。

示例 1：

输出：grid = [[1,3,1],[1,5,1],[4,2,1]]
输入：7
解释：因为门路 1→3→1→1→1 的总和最小。
示例 2：

输出：grid = [[1,2,3],[4,5,6]]
输入：12

提醒：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= gridi <= 100

• 思路：dp[i][j]示意从矩阵左上角到 （i，j） 这个网格对应的最小门路和，只有从上到下，从左到右遍历网格，以后最小门路和就是以后的数值加上下面和右边左小的。
• 复杂度：工夫复杂度O(mn)，m、n 别离是矩阵的长和宽。空间复杂度如果原地批改是O(1)，如果新建 dp 数组就是O(mn)

js：

var minPathSum = function(dp) {let row = dp.length, col = dp[0].length

    for(let i = 1; i < row; i++)// 初始化第一列
        dp[i][0] += dp[i - 1][0]

    for(let j = 1; j < col; j++)// 初始化第一行
        dp[0][j] += dp[0][j - 1]

    for(let i = 1; i < row; i++)
        for(let j = 1; j < col; j++)
            dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1])// 取下面和右边最小的

    return dp[row - 1][col - 1]
};

322. 零钱兑换 (medium)

给你一个整数数组 coins，示意不同面额的硬币；以及一个整数 amount，示意总金额。

计算并返回能够凑成总金额所需的 起码的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你能够认为每种硬币的数量是有限的。

示例 1：

输出：coins = [1, 2, 5], amount = 11
输入：3
解释：11 = 5 + 5 + 1
示例 2：

输出：coins = [2], amount = 3
输入：-1
示例 3：

输出：coins = [1], amount = 0
输入：0

提醒：

1 <= coins.length <= 12
1 <= coins[i] <= 231 – 1
0 <= amount <= 104

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-OXFe4dlO-1678842913185)(null)]

不能用贪婪做，反例，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，则无奈兑换
};

交易股票问题

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 <= 105
0 <= 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 * 104
0 <= 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 <= 105
0 <= 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 <= 100
0 <= prices.length <= 1000
0 <= 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 <= 5000
0 <= 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])

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

残缺代码

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

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

给定一个整数数组 prices，其中 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 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104

状态转移方程

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

残缺代码

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

视频解说：传送门