# 介绍
- 英语：Dynamic programming，简称 DP
- 定义：把问题分解成相对简单的子问题求解的方式
- 思想：问题拆分，分别求解，组合成为整体解
- 核心：找出子问题及其子问题与原问题的关系，即
状态转移方程
状态转移方程
- 把f(n)拆分为f(1),f(2)....f(n-1)
- 如何把f(1)...f(n-1)的解转化为f(n)的解，就是状态转移方程
# 70.爬楼梯
- f(1) = 1
- f(2) = 2 【(1,1),(2)】
- f(3) = 3 【(1,2),(2,1),(1,1,1)】
- f(4) = 5【(1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)】
状态转移方程：f(n) = f(n-1) + f(n-2)
- 求解
时间O(2^n)：【超时】树的深度是n，总共就有【2^n - 1】个节点要计算
空间O(n)：每个节点都要存储
function climbStairs(n) {
if (n < 3) {
return n;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
1
2
3
4
5
6
2
3
4
5
6
时间O(n)：85.95%
空间O(n)：81.13%
function climbStairs(n, map = new Map([[1, 1],[2, 2]])) {
if (map.has(n)) {
return map.get(n);
}
ans = climbStairs(n - 1, map) + climbStairs(n - 2, map);
map.set(n, ans);
return ans
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
- 根据状态转移方程，存储状态解，并用方程拿到f(n)的解
时间O(n)：95.35%
空间O(n)：15.81%
function climbStairs(n) {
const dp = [0, 1, 2];
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n]
}
1
2
3
4
5
6
7
2
3
4
5
6
7
dp[i] = dp[i - 1] + dp[i - 2]
// 所以总是留 前两个值就行
1
2
2
- 空间复杂度优化成O(1)
时间O(n)：98.91%
空间O(1)：94.10%
function climbStairs(n) {
if (n < 3) return n;
let first = 1;
let second = 2;
for (let i = 3; i < n; i++) {
[first, second] = [second, first + second];
}
return first + second;
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 674. 最长连续递增序列
- 求最长连续的递增子序列长度
const nums = [1,3,5,4,7];
console.log(findLengthOfLCIS(nums))
// 输出：3
1
2
3
2
3
时间：96.51%
空间：5.39%
var findLengthOfLCIS = function(nums) {
const dp = [1];
let ans = 1;
for (let i = 1; i < nums.length; i++) {
dp[i] = nums[i] > nums[i - 1] ? dp[i - 1] + 1 : 1;
}
return Math.max(...dp);
};
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
时间：96.51%
空间：39.91%
var findLengthOfLCIS = function(nums) {
let current = 1;
let max = 1;
for (let i = 1; i < nums.length; i++) {
current = nums[i] > nums[i - 1] ? current + 1 : 1;
if (current > max) max = current;
}
return max;
};
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 53.最大子数组和
- 给一个整数数组（可能有负数）
- 求最大子数组的和
const nums = [-2,1,-3,4,-1,2,1,-5,4]
console.log(maxSubArray(nums)); // 6
1
2
2
- (从 i=1 开始)，num[i -1] 如果大于0，num[i]就变成num[i - 1] + num[i]
- 遍历一遍求出最大值
时间O(n)：94.75%
空间O(1)：8.30%
function maxSubArray(num) {
const dp = [num[0]];
let max = num[0];
for (let i = 1; i < num.length; i++) {
dp[i] = dp[i - 1] > 0 ? dp[i - 1] + num[i] : num[i];
max =dp[i] > max ? dp[i] : max;
}
return max;
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
// 总是要连续当前最大和，也就是说上一位是正数就可以加他
dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : num[i]
// 所以只要存动态规划数组前一个值供后一位使用就行
1
2
3
2
3
时间：94.75%
空间：39.35%
function maxSubArray(num) {
let pre = num[0];
let max = num[0];
for (let i = 1; i < num.length; i++) {
pre = pre > 0 ? pre + num[i] : num[i];
max = Math.max(pre, max);
}
return max;
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
- 一个变量保存当前最大和
- 一个变量保存当前连续和
- 当前连续和小于0则丢弃
- 当前连续和大于最大和则替换最大和
时间O(n)：99.83%
空间O(1)：79.10%
function maxSubArray(num) {
let max = num[0];
let currentSum = 0;
for (let i = 0; i < num.length; i++) {
let newSum = currentSum + num[i];
if (newSum > max) {
max = newSum;
}
currentSum = newSum > 0 ? newSum : 0;
}
return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 300.最长递增子序列
- 给一个整数数组
- 找到最长严格递增子序列
const nums = [10,9,2,5,3,7,101,18]
console.log(lengthOfLIS(nums)); // 4 【2，5，7，101】
1
2
2
- 拿一个数组一一对应nums长度，存储每个值的严格递增的个数
- num[i]如果大于前面的某一项，就在那一项的递增数+1，求出每个i对应的递增数的最大值
时间O(n^2)：80.83%
空间O(n)：65.08%
function lengthOfLIS(nums) {
const dp = [1];
for (let i = 1; i < nums.length; i++) {
let cMax = 1;
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[j] + 1 > cMax) {
cMax = dp[j] + 1;
}
}
dp[i] = cMax;
}
return Math.max(...dp);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 509 斐波那契数
// F(0) = 0，F(1) = 1
// F(n) = F(n - 1) + F(n - 2)，其中 n > 1
const n = 2;
console.log(fib(n))
// 输出：1
// 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
1
2
3
4
5
6
2
3
4
5
6
时间：40.88%
空间：14.16%
function fib(n) {
return n === 0 || n === 1 ? n : fib(n - 1) + fib(n - 2)
}
1
2
3
2
3
function tribonacci(n) {
const dp = [];
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n]
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
时间：91.79%
空间：10.56%
function tribonacci(n) {
if (n < 4) {
return n < 2 ? n : n - 1;
}
let one = 0;
let two = 1;
let three = 1;
for (let i = 3; i <= n; i++) {
[one, two, three] = [two, three, one + two + three];
}
return three;
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 1137.第 N 个泰波那契数
- 题 (opens new window):T0 = 0, T1 = 1, T2 = 1,Tn+3 = Tn + Tn+1 + Tn+2
const n = 4;
console.log(tribonacci(n));
// 输出：4
// 解释：
// T_3 = 0 + 1 + 1 = 2
// T_4 = 1 + 1 + 2 = 4
1
2
3
4
5
6
2
3
4
5
6
时间：80.42% 空间：11.51%
function tribonacci(n) {
const arr = [0, 1, 1];
for(let i = 3; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
}
return arr[n];
}
1
2
3
4
5
6
7
2
3
4
5
6
7
- 已经用过的数组实际上用不到，只会用到最后的几个数字。注意把控好几个数字的加减关系
时间：96.68%
空间：13.68%
function tribonacci(n) {
if (n < 2) return n;
if (n === 2) return 1;
let one = 0;
let two = 1;
let three = 1;
for (let i = 4; i <= n; i++) {
const temp = one;
one = two;
two = three;
three = temp + one + two;
}
return one + two + three;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 64.最小路径和
- 给一个n*n的表格，从左上到右下的最小路径和
const grid = [[1,3,1],[1,5,1],[4,2,1]];
console.log(minPathSum(grid));
// 输出：7
// 解释：因为路径 1→3→1→1→1 的总和最小。
1
2
3
4
2
3
4
- 动态规划：制作一个一样的表格，每个位置存储当前最短路径，返回右下数字，即为最短路径。
时间：96.41%
空间：19.01%
function minPathSum(grid) {
const row = grid.length;
const col = grid[0].length;
const ans = Array(row).fill(null);
ans.forEach((item, idx) => ans[idx] = []);
const setMinPath = (i, j) => {
if (i > 0 && j > 0) {
ans[i][j] = Math.min(ans[i - 1][j], ans[i][j - 1]) + grid[i][j];
} else if (i > 0) {
ans[i][j] = ans[i - 1][j] + grid[i][j];
} else if (j > 0) {
ans[i][j] = ans[i][j - 1] + grid[i][j];
} else {
ans[i][j] = grid[i][j];
}
}
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
setMinPath(i, j);
}
}
return ans[row - 1][col - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 17.电话
- 九宫格电话输入后有多少种排列方式
const digits = "23"
console.log(letterCombinations(digits));
// ["ad","ae","af","bd","be","bf","cd","ce","cf"]
1
2
3
2
3
时间：95.72%
空间：11.18%
- 二层遍历，做二维数组，然后再打平。
function letterCombinations(digits) {
if (digits === '') return [];
const deps = {
[2]: ['a', 'b', 'c'],
[3]: ['d', 'e', 'f'],
[4]: ['g', 'h', 'i'],
[5]: ['j', 'k', 'l'],
[6]: ['m', 'n', 'o'],
[7]: ['p', 'q', 'r', 's'],
[8]: ['t', 'u', 'v'],
[9]: ['w', 'x', 'y', 'z'],
};
const digitArr = digits.split('').map(item => +item);
return digitArr.reduce((pre, item) => {
let dep = deps[item];
if (!pre) {
return [...dep];
}
return dep.map(item => pre.map(i => i + item)).flat(2);
}, null)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 746.最小花费爬楼梯
- 花一次钱跳1-2格，最小花费跳到结束
const arr = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1];
console.log(minCostClimbingStairs(arr));
1
2
2
const arr = [10, 15, 20];
console.log(minCostClimbingStairs(arr));
1
2
2
- 思路：每一格都求出到当前格的最便宜的走法（前一格、前两格中便宜的那个 + 自己）。最后拿dp最后两个花费的小的那个值就能走出去。
时间：95.84%
空间：10.26%
function minCostClimbingStairs(arr) {
if (arr.length < 3) {
return Math.min(...arr);
}
const dp = [arr[0], arr[1]];
const len = arr.length;
for (let i = 2; i < len; i++) {
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + arr[i];
}
return Math.min(dp[len - 1], dp[len - 2])
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
- 一样，动态规划只用到数组的最后两个值，所以可以直接用动态变量存
时间：98.58%
空间：20.74%
function minCostClimbingStairs(cost) {
if (cost.length < 3) {
return Math.min(...cost);
}
let first = cost[0];
let second = cost[1];
for (let i = 2; i < cost.length; i++) {
const temp = first;
first = second;
second = Math.min(temp, first) + cost[i];
}
return Math.min(first, second);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 198.打家劫舍
- 小偷不能偷相邻的房子，求能偷得最多钱
const i = [1,2,3,1];
console.log(rob(i)); // 4
const i2 = [2,7,9,3,1];
console.log(rob(i2)); // 12
1
2
3
4
5
2
3
4
5
- 必须隔一家，那么最多隔两家，因为隔三家就是傻子，浪费一家没偷。
时间：98.86%
空间：5.74%
function rob(nums) {
if (nums.length < 3) {
return Math.max(...nums);
}
const dp = [nums[0], nums[1]];
const setDp = idx => {
let first = idx > 2 ? dp[idx - 3] : 0;
let second = dp[idx - 2];
dp[idx] = Math.max(first, second) + nums[idx];
}
for (let i = 2; i < nums.length; i++) {
setDp(i);
}
return Math.max(dp[dp.length - 1], dp[dp.length - 2]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
- 指针优化
时间：98.86%
空间：19.51%
function rob(nums) {
if (nums.length < 3) {
return Math.max(...nums);
}
let first = nums[0];
let second = nums[1];
let three = 0;
const setTemp = (idx) => {
const temp = Math.max(first, second) + nums[idx];
first = second;
second = three;
three = temp;
}
for (let i = 2; i < nums.length; i++) {
setTemp(i);
}
return Math.max(first, second);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 213.打家劫舍2
- 屋子围城一圈，要不偷相邻房间的情况下偷最多
const nums = [2,3,2];
console.log(rob(nums)); // 3
1
2
2
- 环拆成两个数组，0~n-1, 1~n，动态算两遍，取出最大的
99.74%
5.47%
function rob(nums) {
if (nums.length < 4) return Math.max(...nums);
const dynamic = (subNums) => {
let one = 0;
let two = subNums[0];
let three = subNums[1];
const setNext = idx => {
const temp = Math.max(one, two) + subNums[idx];
one = two;
two = three;
three = temp;
}
for (let i = 0; i < subNums; i++) {
setNext(i);
}
return Math.max(two, three);
}
const ans1 = dynamic(nums.slice(0, -1));
const ans2 = dynamic(nums.slice(1));
return Math.max(ans1, ans2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
- 思路一样，环变成两个数组，然后计算选出大的值。但是空间消耗太大了，修改动态规划方程。
时间：100%
空间：5.02
??空间没变？
function rob(nums) {
if (nums.length < 4) return Math.max(...nums);
const dynamic = (start, end) => {
let one = 0;
let two = nums[start];
let three = nums[start + 1];
for (let i = start + 2; i < end; i++) {
const temp = Math.max(two, three) + nums[i];
one = two;
two = three;
three = temp;
}
return Math.max(two, three);
}
const ans1 = dynamic(0, nums.length - 1);
const ans2 = dynamic(1, nums.length);
return Math.max(ans1, ans2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 740. 删除并获得点数
- 获取点数n，删除所有n-1, n+1，求最大值
const nums = [2,2,3,3,3,4];
console.log(deleteAndEarn(nums)); // 9
1
2
2
- 思路：做一个最大数作为长度的数组。数组第i项的值代表nums里面所有i的和。再对应这个数组做dp。
时间：99.06%
空间：27.63%
function deleteAndEarn(nums) {
const max = Math.max(...nums);
const sum = Array(max + 1).fill(0);
const dp = Array(max + 1).fill(0);
nums.forEach(i => sum[i] += i);
dp[1] = sum[1];
for (let i = 2; i < dp.length; i++) {
dp[i] = Math.max(dp[i - 1], sum[i] + dp[i - 2]);
}
return dp[max];
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 55. 跳跃游戏
- 从左跳到右，每一格代表能跳的步数，看是否能到右边
const nums = [3,2,1,0,4]
console.log(canJump(nums));
// 输出：false
1
2
3
2
3
时间：99.14%
空间：5.02%
function canJump(nums) {
const dp = [...nums];
for (let i = 1; i < dp.length - 1; i++) {
dp[i] = Math.max(dp[i - 1] - 1, dp[i]);
}
return !dp.slice(0, -1).includes(0);
}
1
2
3
4
5
6
7
2
3
4
5
6
7
# 45. 跳跃游戏 II
- 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
- 假设你总是可以到达数组的最后一个位置。
const nums = [2,3,1,1,4];
console.log(jump(nums));
// 输出: 2
1
2
3
2
3
时间：92.96%
空间：21.48%
function jump(arr) {
let maxPosition = 0;
let end = 0;
let step = 0;
// len - 1，因为要少遍历一次，到最后一个点就可以了
for (let i = 0; i < arr.length - 1; i++) {
// 核心：总是记录当前步数内下一步能到达的最远位置
maxPosition = Math.max(maxPosition, i + arr[i]);
// 到达上个最远位置了，加一个step换上当前能到的最远值，如果达标就返回。
if (i === end) {
step++;
end = maxPosition;
if (end > arr.length) {
return step;
}
}
}
return step;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 152.最大乘积子数组
- 连续的，最大乘积的，子数组
const nums = [2,3,-2,4]
console.log(maxProduct(nums));
// 输出: 6
// 解释: 子数组 [2,3] 有最大乘积 6。
1
2
3
4
2
3
4
- 重点：动态规划要考虑两个负数相隔很远的情况
用两个动态规划数组分别存储最大值最小值
时间：96.48%
空间：8.73%
function maxProduct(nums) {
const maxDp = [nums[0]];
const minDp = [nums[0]];
for (let i = 1; i < nums.length; i++) {
maxDp[i] = Math.max(nums[i], nums[i] * maxDp[i - 1], nums[i] * minDp[i - 1]);
minDp[i] = Math.min(nums[i], nums[i] * maxDp[i - 1], nums[i] * minDp[i - 1]);
}
return Math.max(...maxDp);
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
时间：96.48%
空间：19.12%
function maxProduct(nums) {
let max = nums[0];
let min = nums[0];
let ans = nums[0];
for (let i = 1; i < nums.length; i++) {
// 因为下面就要赋值，所以先暂存上次的最大/小值
const [mx, mn] = [max, min];
max = Math.max(nums[i] * mx, nums[i] * mn, nums[i]);
min = Math.min(nums[i] * mx, nums[i] * mn, nums[i]);
ans = Math.max(max, ans);
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 1567. 积为正数子数组长度
- 连续相乘，积为正数，最长子数组长度
const nums = [1, -2, -3, 4]; // 4
// const nums = [0, 1, -2, -3, -4]; // 3
// const nums = [1, 2, 3, 5, -6, 4, 0, 10]; // 4
// const nums = [-1, 2]; // 1
console.log(getMaxLen(nums));
1
2
3
4
5
2
3
4
5
- 一个正数长度，一个负数长度，一起向前加，遇到负数正负互换
时间：95.60%
空间：39.60%
function getMaxLen(nums) {
let max = 0;
let z = 0;
let f = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 0) {
z = 0;
f = 0;
} else if (nums[i] > 0) {
z++;
f += f > 0 ? 1 : 0; // 细节判断，负数有才让他加
max = Math.max(z, max);
} else {
[z, f] = [f, z];
f++;
z += z > 0 ? 1 : 0; // 细节判断，正数有才让他加
max = Math.max(z, max);
}
}
return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 1014. 最佳观光组合
- 一对景点（i < j）组成的观光组合的得分为
values[i] + values[j] + i - j，也就是景点的评分之和 减去 它们两者之间的距离。 - 求最大值
const values = [8,1,5,2,6];
console.log(maxScoreSightseeingPair(nums));
// 输出：11
1
2
3
2
3
- 常规动态规划，时间太长O(n^2)
时间：7.14%
空间：6.83%
function maxScoreSightseeingPair(values) {
const dp = [values[0]];
for (let i = 1; i < values.length; i++) {
let cMax = 0;
for (let j = 0; j < i; j++) {
const cVal = values[i] + values[j] - (i - j);
cMax = Math.max(cVal, cMax);
}
dp[i] = cMax;
}
return Math.max(...dp);
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
// 状态转移方程：
dp[i] = val[i] + val[j] - (i - j)
// 变形：
dp[i] = val[i] - i + (j + val[j])
// 要最大值，所以 j + val[j] 留最大
1
2
3
4
5
2
3
4
5
时间：90.06%
空间：21.74%
function maxScoreSightseeingPair(val) {
let maxLeft = val[0] + 0;
let max = 0;
for (let i = 1; i < val.length; i++) {
const cVal = val[i] - i + maxLeft;
max = Math.max(max, cVal);
maxLeft = Math.max(val[i] + i, maxLeft);
}
return max;
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 121. 买卖股票的最佳时机
- 一个数组，每天的股价，只有一次买卖机会，求最大利润
const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices));
1
2
2
- 思路：总是拿到当前能减的最小值，就能求出当前卖出的最大利润
// 动态规划公式
dp[i] = Math.min(dp[i - 1], nums[i]);
// 所以只要收集最小值就行
1
2
3
2
3
时间：99.59%
空间：38.94%
var maxProfit = function (prices) {
let cLower = prices[0];
let max = 0;
for (let i = 1; i < prices.length; i++) {
cLower = Math.min(cLower, prices[i]);
max = Math.max(prices[i] - cLower, max);
}
return max;
};
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 122. 买卖股票的最佳时机 II
- 一次只能持有一只股票，随便买入卖出几次
- 贪心最暴力：只要是上升曲线，就吃
时间：91.26%
空间：33.32%
var maxProfit = function(prices) {
let profit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
};
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
- 乖乖动态规划
// 动态公式
dp[i] = num[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0)
// 上一个利润大于0就+
1
2
3
2
3
时间：96.62%
空间：8.89%
var maxProfit = function(prices) {
let dp = [0];
const len = prices.length;
for (let i = 1; i < len; i++) {
const cProfit = prices[i] - prices[i - 1];
dp[i] = dp[i - 1] + (cProfit > 0 ? cProfit : 0)
}
return dp[len - 1];
};
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
- 动态指针优化
时间：99.79%
空间：44.00%
var maxProfit = function(prices) {
let max = 0;
const len = prices.length;
for (let i = 1; i < len; i++) {
const cProfit = prices[i] - prices[i - 1];
max += cProfit > 0 ? cProfit : 0;
}
return max;
};
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 118. 杨辉三角
- 生成指定长度的杨辉三角
const numRows = 5
console.log(generate(numRows));
// 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
1
2
3
2
3
// 动态公式
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; // 1 < j < cLen - 1
dp[i][j] = 1; // [0][0] [1][0] [1][1]
1
2
3
2
3
时间：98.44%
空间：38.53%
var generate = function(numRows) {
let ans = [[1]];
for (let i = 1; i < numRows; i++) {
let cRow = Array(i + 1).fill(1);
for (let j = 1; j < cRow.length - 1; j++) {
const first = ans[i - 1][j - 1] ? ans[i - 1][j - 1] : 0;
const second = ans[i - 1][j];
cRow[j] = first + second;
}
ans.push(cRow);
}
return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 931. 下降路径最小和
- 二维矩阵，只能向下或斜向下走，求最小和
const matrix = [[2,1,3],[6,5,4],[7,8,9]];
console.log(minFallingPathSum(matrix)); // 13
// 输出：13
1
2
3
2
3
// 状态转移方程：
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + num[i][j];
// 注意边界情况就行
1
2
3
2
3
时间：89.67%
空间：21.27%
var minFallingPathSum = function(matrix) {
const n = matrix.length;
const dp = [matrix[0]];
for (let i = 1; i < n; i++) {
dp[i] = [];
for (let j = 0; j < n; j++) {
let first = dp[i - 1][j - 1] != undefined ? dp[i - 1][j - 1] : Infinity;
let second = dp[i - 1][j];
let thired = dp[i - 1][j + 1] != undefined ? dp[i - 1][j + 1] : Infinity;
const min = Math.min(first, second, thired);
dp[i][j] = matrix[i][j] + min;
}
}
return Math.min(...dp[n - 1]);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
- 只用到了上一层数组，留一层就行
时间：96.35%
空间：35.86%
var minFallingPathSum = function(matrix) {
const n = matrix.length;
let pre = matrix[0];
let ans = matrix[0];
for (let i = 1; i < n; i++) {
ans = [];
for (let j = 0; j < n; j++) {
let first = pre[j - 1] != undefined ? pre[j - 1] : Infinity;
let second = pre[j];
let thired = pre[j + 1] != undefined ? pre[j + 1] : Infinity;
ans[j] = matrix[i][j] + Math.min(first, second, thired);
}
pre = ans;
}
return Math.min(...ans);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 42. 接雨水
const height = [0,1,0,2,1,0,1,3,2,1,2,1]
console.log(trap(height));
// 输出：6
1
2
3
2
3
- 思路：
- 从左往右做一个边界dp，拿到每个位置左边最大值
- 从右往左做一个边界dp，拿到每个位置右边最大值
- 遍历每个位置，左右边界的小值就是当前桶桶的边界，减去当前高度就是当前桶的容量。注意规避负值边界
时间：83.51%
空间：18.27%
var trap = function(height) {
const len = height.length;
const left = Array(len).fill(0);
const right = Array(len).fill(0);
for (let i = 1; i < len; i++) {
left[i] = Math.max(left[i - 1], height[i - 1]);
}
for (let i = len - 2; i >= 0; i--) {
right[i] = Math.max(right[i + 1], height[i + 1]);
}
return height.reduce((pre, item, i) => {
const c = Math.min(left[i], right[i]) - item;
return pre + (c > 0 ? c : 0);
}, 0);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 1143. 最长公共子序列
text1 = "abcde", text2 = "ace"
console.log(longestCommonSubsequence(text1, text2));
// 输出：3
1
2
3
2
3
- 思想：
- 制作二维表，因为可以删除，所以要一层一层往下推，每两个数字之间都要进行比较
- 判断相等的时候，要
dp[i - 1][j - 1] + 1，因为不能是上一个比较过的数字，向下推进的过程中才不会复用计数 - 判断不想等的时候，要根据动态规划思想，继承上一层的最大值，可能在左边，也可能在上面，推到右下角才能是正确的最大值
时间：17.45%
空间：22.90%
const longestCommonSubsequence = (text1, text2) => {
const dp = Array(text1.length).fill().map(() => Array(text2.length).fill(0));
for (let i = 0; i < text1.length; i++) {
for (let j = 0; j < text2.length; j++) {
if (text1[i] === text2[j]) {
dp[i][j] = (dp[i - 1]?.[j - 1] ?? 0) + 1;
} else {
dp[i][j] = Math.max((dp[i - 1]?.[j] ?? 0), (dp[i][j - 1] ?? 0));
}
}
}
return dp[text1.length - 1][text2.length - 1];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
- 思路：在原基础上进行优化：每层计算只需要使用到上一层的结果，那么只需要保存上一层的结果就可以
时间：71.36%
空间：97.88%
const longestCommonSubsequence = (text1, text2) => {
let dp = Array(text1.length).fill(0);
for (let i = 0; i < text2.length; i++) {
let newDp = [];
for (let j = 0; j < text1.length; j++) {
if (text2[i] === text1[j]) {
newDp[j] = (dp[j - 1] ?? 0) + 1;
} else {
newDp[j] = Math.max((newDp[j - 1] ?? 0), (dp[j] ?? 0));
}
}
dp = newDp;
}
return dp[dp.length - 1];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15