什么是动态规划
动态规划,英文:Dynamic Programming
,简称DP
,将问题分解为互相重叠的子问题,通过反复求解子问题来解决原问题就是动态规划,如果某一问题有很多重叠子问题,使用动态规划来解是比较有效的。
求解动态规划的核心问题是穷举,但是这类问题穷举有点特别,因为这类问题存在「重叠子问题」,如果暴力穷举的话效率会极其低下。动态规划问题一定会具备「最优子结构」,才能通过子问题的最值得到原问题的最值。另外,虽然动态规划的核心思想就是穷举求最值,但是问题可以千变万化,穷举所有可行解其实并不是一件容易的事,只有列出正确的「状态转移方程」才能正确地穷举。重叠子问题、最优子结构、状态转移方程就是动态规划三要素
动态规划和其他算法的区别
动态规划和分治的区别:动态规划和分治都有最优子结构 ,但是分治的子问题不重叠
动态规划和贪心的区别:动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优解,所以它永远是局部最优,但是全局的解不一定是最优的。
动态规划和递归的区别:递归和回溯可能存在非常多的重复计算,动态规划可以用递归加记忆化的方式减少不必要的重复计算
动态规划的解题方法
解动态规划题目的步骤
根据重叠子问题定义状态
寻找最优子结构推导状态转移方程
确定 dp 初始状态
确定输出值
斐波那契的动态规划的解题思路
动画过大,点击查看
暴力递归
//暴力递归复杂度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;
};
复制代码
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符删除一个字符替换一个字符
示例 1:
输入:word1 = "horse", word2 = "ros"输出:3 解释:horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')示例 2:
输入:word1 = "intention", word2 = "execution"输出:5 解释:intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')
提示:
0 <= word1.length, word2.length <= 500word1 和 word2 由小写英文字母组成
方法 1.动态规划
思路:dp[i][j]
表示 word1 前 i 个字符和 word2 前 j 个字符的最少编辑距离。
如果word1[i-1] === word2[j-1]
,说明最后一个字符不用操作,此时dp[i][j] = dp[i-1][j-1]
,即此时的最小操作数和 word1 和 word2 都减少一个字符的最小编辑数相同
如果word1[i-1] !== word2[j-1]
,则分为三种情况
word1 删除最后一个字符,状态转移成dp[i-1][j]
,即dp[i][j] = dp[i-1][j] + 1
,+1 指删除操作
word1 在最后加上一个字符,状态转移成dp[i][j-1]
,即dp[i][j] = dp[i][j-1] + 1
,+1 指增加操作
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];
};
复制代码
有 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.length1 <= n <= 3000 <= nums[i] <= 100
方法 1:动态规划
思路: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];
};
复制代码
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 2 输出:2 解释:有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2:
输入:n = 3 输出:3 解释:有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
提示:
1 <= n <= 45
方法 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;
}
复制代码
给定一个正整数 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];
};
复制代码
给定一个包含非负整数的 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.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
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]
};
复制代码
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 1:
输入:m = 3, n = 7 输出:28 示例 2:
输入:m = 3, n = 2 输出:3 解释:从左上角开始,总共有 3 条路径可以到达右下角。
向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下
示例 3:
输入:m = 7, n = 3 输出:28 示例 4:
输入:m = 3, n = 3 输出:6
提示:
1 <= m, n <= 100 题目数据保证答案小于等于 2 * 109
方法 1.动态规划
动画过大,点击查看
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];
};
复制代码
0-1 背包问题
0-1 背包问题指的是有n
个物品和容量为j
的背包,weight
数组中记录了n
个物品的重量,位置i
的物品重量是 weight[i],value
数组中记录了n
个物品的价值,位置 i 的物品价值是vales[i]
,每个物品只能放一次到背包中,问将那些物品装入背包,使背包的价值最大。
举例:
我们用动态规划的方式来做
状态定义:dp[i][j]
表示从前 i 个物品里任意取,放进容量为 j 的背包,价值总和最大是多少
状态转移方程: dp[i][j] = max(dp[i - 1][j]
, dp[i - 1][j - weight[i]] + value[i])
; 每个物品有放入背包和不放入背包两种情况
当j - weight[i]<0
:表示装不下i
号元素了,不放入背包,此时dp[i][j] = dp[i - 1][j]
,dp[i] [j]取决于前i-1
中的物品装入容量为j
的背包中的最大价值
当j - weight[i]>=0
:可以选择放入或者不放入背包。放入背包则:dp[i][j] = dp[i - 1][j - weight[i]] + value[i]
, dp[i - 1][j - weight[i]]
表示i-1
中的物品装入容量为j-weight[i]
的背包中的最大价值,然后在加上放入的物品的价值value[i]
就可以将状态转移到dp[i][j]
。不放入背包则:dp[i][j] = dp[i - 1] [j]
,在这两种情况中取较大者。
初始化 dp 数组:dp[i][0]
表示背包的容积为 0,则背包的价值一定是 0,dp[0][j]
表示第 0 号物品放入背包之后背包的价值
最终需要返回值:就是 dp 数组的最后一行的最后一列
循环完成之后的 dp 数组如下图
js:
function testWeightBagProblem(wight, value, size) {
const len = wight.length,
dp = Array.from({ length: len + 1 }).map(//初始化dp数组
() => Array(size + 1).fill(0)
);
//注意我们让i从1开始,因为我们有时会用到i - 1,为了防止数组越界
//所以dp数组在初始化的时候,长度是wight.length+1
for (let i = 1; i <= len; i++) {
for (let j = 0; j <= size; j++) {
//因为weight的长度是wight.length+1,并且物品下标从1开始,所以这里i要减1
if (wight[i - 1] <= j) {
dp[i][j] = Math.max(
dp[i - 1][j],
value[i - 1] + dp[i - 1][j - wight[i - 1]]
)
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[len][size];
}
function test() {
console.log(testWeightBagProblem([1, 3, 4], [15, 20, 30], 4));
}
test();
复制代码
状态压缩
根据状态转移方程dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
,第 i 行只与第 i-1 行状态相关,所以我们可以用滚动数组进行状态压缩,其次我们注意到,j 只与 j 前面的状态相关,所以只用一个数组从后向前计算状态就可以了。
动画过大,点击查看
function testWeightBagProblem2(wight, value, size) {
const len = wight.length,
dp = Array(size + 1).fill(0);
for (let i = 1; i <= len; i++) {
//从后向前计算,如果从前向后的话,最新的值会覆盖老的值,导致计算结果不正确
//dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wight[i - 1]] + value[i - 1])
for (let j = size; j >= wight[i - 1]; j--) {
dp[j] = Math.max(dp[j], dp[j - wight[i - 1]] + value[i - 1] );
}
}
return dp[size];
}
复制代码
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5]输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。示例 2:
输入:nums = [1,2,3,5]输出:false 解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 2001 <= nums[i] <= 100
思路:本题可以看成是 0-1 背包问题,给一个可装载重量为 sum / 2
的背包和 N 个物品,每个物品的重量记录在 nums 数组中,问是否在一种装法,能够恰好将背包装满?dp[i][j]
表示前 i 个物品是否能装满容积为 j 的背包,当dp[i][j]
为 true 时表示恰好可以装满。每个数都有放入背包和不放入两种情况,分析方法和 0-1 背包问题一样。
复杂度:时间复杂度O(n*sum)
,n 是 nums 数组长度,sum 是 nums 数组元素的和。空间复杂度O(n * sum)
,状态压缩之后是O(sum)
js:
//可以看成是0-1背包问题,给一个可装载重量为 sum / 2 的背包和 N 个物品,
//每个物品的重量记录在 nums 数组中,问是否在一种装法,能够恰好将背包装满?
var canPartition = function (nums) {
let sum = 0
let n = nums.length
for (let i = 0; i < n; i++) {
sum += nums[i]
}
if (sum % 2 !== 0) {//如果是奇数,那么分割不了,直接返回false
return false
}
sum = sum / 2
//dp[i][j]表示前i个物品是否能装满容积为j的背包,当dp[i][j]为true时表示恰好可以装满
//最后求的是 dp[n][sum] 表示前n个物品能否把容量为sum的背包恰好装满
//dp数组长度是n+1,而且是二维数组,第一维表示物品的索引,第二个维度表示背包大小
let dp = new Array(n + 1).fill(0).map(() => new Array(sum + 1).fill(false))
//dp数组初始化,dp[..][0] = true表示背包容量为0,这时候就已经装满了,
//dp[0][..] = false 表示没有物品,肯定装不满
for (let i = 0; i <= n; i++) {
dp[i][0] = true
}
for (let i = 1; i <= n; i++) {//i从1开始遍历防止取dp[i - 1][j]的时候数组越界
let num = nums[i - 1]
//j从1开始,j为0的情况已经在dp数组初始化的时候完成了
for (let j = 1; j <= sum; j++) {
if (j - num < 0) {//背包容量不足 不能放入背包
dp[i][j] = dp[i - 1][j];//dp[i][j]取决于前i-1个物品是否能前好装满j的容量
} else {
//dp[i - 1][j]表示不装入第i个物品
//dp[i - 1][j-num]表示装入第i个,此时需要向前看前i - 1是否能装满j-num
//和背包的区别,这里只是返回true和false 表示能否装满,不用计算价值
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
}
}
}
return dp[n][sum]
};
//状态转移方程 F[i, target] = F[i - 1, target] || F[i - 1, target - nums[i]]
//第 n 行的状态只依赖于第 n-1 行的状态
//状态压缩
var canPartition = function (nums) {
let sum = nums.reduce((acc, num) => acc + num, 0);
if (sum % 2) {
return false;
}
sum = sum / 2;
const dp = Array.from({ length: sum + 1 }).fill(false);
dp[0] = true;
for (let i = 1; i <= nums.length; i++) {
//从后向前计算,如果从前向后的话,最新的值会覆盖老的值,导致计算结果不正确
for (let j = sum; j > 0; j--) {
dp[j] = dp[j] || (j - nums[i] >= 0 && dp[j - nums[i]]);
}
}
return dp[sum];
};
复制代码
买卖股票问题
第 5,6 道题相当于在第 2 道题的基础上加了冷冻期和手续费的条件。
限制条件
先买入才能卖出
不能同时参加多笔交易,再次买入时,需要先卖出
k >= 0
才能进行交易,否则没有交易次数
定义操作
定义状态
举例
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])
//最大利润就是这俩种情况的最大值
复制代码
给定一个数组 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 <= 1050 <= 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;
};
复制代码
给你一个整数数组 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 * 1040 <= 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;
};
复制代码
给定一个数组,它的第 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 <= 1050 <= 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
}
复制代码
给定一个整数数组 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 <= 1000 <= prices.length <= 10000 <= 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次清空手中的股票之后的最大利润
};
复制代码
给定一个整数数组 prices,其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: prices = [1,2,3,0,2]输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]示例 2:
输入: prices = [1]输出: 0
提示:
1 <= prices.length <= 50000 <= 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;
};
复制代码
给定一个整数数组 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 * 1041 <= prices[i] < 5 * 1040 <= 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;
};
复制代码
给你一个整数数组 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 <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
不能用贪心做,反例,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,则无法兑换
};
复制代码
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]输出:2 解释:3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径:
向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右
示例 2:
输入:obstacleGrid = [[0,1],[0,0]]输出:1
提示:
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j] 为 0 或 1
方法 1.动态规划
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];
};
复制代码
视频讲解:传送门
评论