大廠算法面試之leetcode精講3.動態(tài)規(guī)劃
視頻教程（高效學習）:點擊學習
目錄：
什么是動態(tài)規(guī)劃
動態(tài)規(guī)劃，英文：Dynamic Programming惋嚎，簡稱DP罗捎，將問題分解為互相重疊的子問題涌攻，通過反復求解子問題來解決原問題就是動態(tài)規(guī)劃，如果某一問題有很多重疊子問題闷煤，使用動態(tài)規(guī)劃來解是比較有效的导街。
求解動態(tài)規(guī)劃的核心問題是窮舉，但是這類問題窮舉有點特別踪蹬，因為這類問題存在「重疊子問題」，如果暴力窮舉的話效率會極其低下臣咖。動態(tài)規(guī)劃問題一定會具備「最優(yōu)子結構」跃捣，才能通過子問題的最值得到原問題的最值。另外夺蛇，雖然動態(tài)規(guī)劃的核心思想就是窮舉求最值疚漆，但是問題可以千變萬化，窮舉所有可行解其實并不是一件容易的事，只有列出正確的「狀態(tài)轉移方程」才能正確地窮舉娶聘。重疊子問題闻镶、最優(yōu)子結構、狀態(tài)轉移方程就是動態(tài)規(guī)劃三要素
動態(tài)規(guī)劃和其他算法的區(qū)別
- 動態(tài)規(guī)劃和分治的區(qū)別：動態(tài)規(guī)劃和分治都有最優(yōu)子結構 丸升，但是分治的子問題不重疊
- 動態(tài)規(guī)劃和貪心的區(qū)別：動態(tài)規(guī)劃中每一個狀態(tài)一定是由上一個狀態(tài)推導出來的铆农，這一點就區(qū)分于貪心，貪心沒有狀態(tài)推導狡耻，而是從局部直接選最優(yōu)解墩剖，所以它永遠是局部最優(yōu)，但是全局的解不一定是最優(yōu)的夷狰。
- 動態(tài)規(guī)劃和遞歸的區(qū)別：遞歸和回溯可能存在非常多的重復計算岭皂，動態(tài)規(guī)劃可以用遞歸加記憶化的方式減少不必要的重復計算
動態(tài)規(guī)劃的解題方法
- 遞歸+記憶化(自頂向下)
- 動態(tài)規(guī)劃（自底向上）
ds_135
解動態(tài)規(guī)劃題目的步驟
- 根據重疊子問題定義狀態(tài)
- 尋找最優(yōu)子結構推導狀態(tài)轉移方程
- 確定dp初始狀態(tài)
- 確定輸出值
斐波那契的動態(tài)規(guī)劃的解題思路
ds_3
暴力遞歸
//暴力遞歸復雜度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] = fib(x - 1) + fib(x - 2);
return memo[x];
};
return helper(n);
};
動態(tài)規(guī)劃
const fib = (n) => {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
//自底向上計算每個狀態(tài)
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
滾動數組優(yōu)化
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;
};
動態(tài)規(guī)劃 + 降維瘫证，（降維能減少空間復雜度，但不利于程序的擴展）
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;
};
509. 斐波那契數（easy）
方法1.動態(tài)規(guī)劃
- 思路：自底而上的動態(tài)規(guī)劃
- 復雜度分析：時間復雜度
O(n)庄撮，空間復雜度O(1)
Js:
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;
};
Java:
class Solution {
public int fib(int n) {
if (n <= 1) {
return n;
}
int prev2 = 0, prev1 = 1, result = 0;
for (int i = 2; i <= n; i++) {
result = prev2 + prev1;
prev2 = prev1;
prev1 = result;
}
return result;
}
}
62. 不同路徑 （medium）
方法1.動態(tài)規(guī)劃
- 思路:由于在每個位置只能向下或者向右， 所以每個坐標的路徑和等于上一行相同位置和上一列相同位置不同路徑的總和洞斯，狀態(tài)轉移方程：
f[i][j] = f[i - 1][j] + f[i][j - 1]; - 復雜度:時間復雜度
O(mn)毡庆。空間復雜度O(mn)烙如，優(yōu)化后O(n)
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];
};
//狀態(tài)壓縮
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];
};
Java:
class Solution {
public int uniquePaths(int m, int n) {
int[][] f = new int[m][n];
for (int i = 0; i < m; ++i) {
f[i][0] = 1;
}
for (int j = 0; j < n; ++j) {
f[0][j] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
}
//狀態(tài)壓縮
class Solution {
public int uniquePaths(int m, int n) {
int[] cur = new int[n];
Arrays.fill(cur,1);
for (int i = 1; i < m;i++){
for (int j = 1; j < n; j++){
cur[j] += cur[j-1] ;
}
}
return cur[n-1];
}
}
63. 不同路徑 II（medium）
方法1.動態(tài)規(guī)劃
- 思路：和62題一樣么抗，區(qū)別就是遇到障礙直接返回0
- 復雜度：時間復雜度
O(mn)，空間復雜度O(mn)亚铁，狀態(tài)壓縮之后是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];
};
//狀態(tài)壓縮
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];
};
Java:
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length, m = obstacleGrid[0].length;
int[] dp = new int[m];
dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
continue;
}
if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
dp[j] += dp[j - 1];
}
}
}
return dp[m - 1];
}
}
70. 爬樓梯 （medium）
方法1.動態(tài)規(guī)劃
ds_71
- 思路：因為每次可以爬 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];
};
//狀態(tài)壓縮
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;
}
Java:
class Solution {
public int climbStairs(int n) {
int prev = 1, cur = 1;
for (int i = 2; i < n + 1; i++) {
int temp = cur;
cur = prev + cur;
prev = temp;
}
return cur;
}
}
279. 完全平方數 (medium)
ds_204
方法1:動態(tài)規(guī)劃
思路：
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是輸入的整數，需要循環(huá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++) {//枚舉前一個狀態(tài)
dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 動態(tài)轉移方程
}
}
return dp[n];
};
java：
class Solution {
public int numSquares(int n) {
int[] dp = new int[n];
for (int i = 1; i <= n; i++) {
dp[i] = i;
for (int j = 1; i - j * j >= 0; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}
120. 三角形最小路徑和（medium）
方法1.動態(tài)規(guī)劃
ds_72
- 思路：從三角形最后一層開始向上遍歷，每個數字的最小路徑和是它下面兩個數字中的較小者加上它本身
- 復雜度分析：時間復雜度
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 { // 狀態(tài)轉移方程检盼，上一層由它下面一層計算出
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
}
}
}
return dp[0][0];
};
//狀態(tài)壓縮
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];
};
Java:
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int [] dp = new int [n];
for(int i = 0 ; i < n ; i++){
dp[i] = triangle.get(n-1).get(i);
}
for(int i = n-2 ; i >= 0 ; i--){
for(int j = 0 ; j <= i ; j++){
dp[j] = triangle.get(i).get(j) + Math.min(dp[j] , dp[j+1]);//迭代
}
}
return dp[0];
}
}
152. 乘積最大子數組 （medium）
方法1.動態(tài)規(guī)劃
ds_73
-
思路：
狀態(tài)定義：
dp[i][0]表示從第 0 項到第 i 項范圍內的子數組的最小乘積，dp[i][1]表示從第 0 項到第 i 項范圍內的子數組的最大乘積初始狀態(tài)：
dp[0][0]=nums[0], dp[0][1]=nums[0]-
分情況討論:
- 不和別人乘翘单，就
nums[i]自己 -
num[i]是負數吨枉，希望乘上前面的最大積 -
num[i]是正數，希望乘上前面的最小積
- 不和別人乘翘单，就
-
狀態(tài)轉移方程：
- dp[i] [0]=min(dp[i?1] [0]?num[i] , dp[i?1] [1] ? num[i], num[i])
- dp[i] [1]=max(dp[i?1] [0]?num[i] , dp[i?1] [1] ? num[i], num[i])
狀態(tài)壓縮：
dp[i][x]只與dp[i][x]-1哄芜，所以只需定義兩個變量貌亭，prevMin = nums[0]，prevMax = nums[0]-
狀態(tài)壓縮之后的方程：
- prevMin = Math.min(prevMin * num[i], prevMax * num[i], nums[i])
- prevMax = Math.max(prevMin * num[i], prevMax * num[i], nums[i])
- 復雜度：時間復雜度
O(n)认臊，空間復雜度O(1)
js:
var maxProduct = (nums) => {
let res = nums[0]
let prevMin = nums[0]
let prevMax = nums[0]
let temp1 = 0, temp2 = 0
for (let i = 1; i < nums.length; i++) {
temp1 = prevMin * nums[i]
temp2 = prevMax * nums[i]
prevMin = Math.min(temp1, temp2, nums[i])
prevMax = Math.max(temp1, temp2, nums[i])
res = Math.max(prevMax, res)
}
return res
}
Java:
class Solution {
public int maxProduct(int[] nums) {
int res = nums[0], prevMin = nums[0], prevMax = nums[0];
int temp1 = 0, temp2 = 0;
for (int i = 1; i < nums.length; i++) {
temp1 = prevMin * nums[i];
temp2 = prevMax * nums[i];
prevMin = Math.min(Math.min(temp1, temp2), nums[i]);
prevMax = Math.max(Math.max(temp1, temp2), nums[i]);
res = Math.max(prevMax, res);
}
return res;
}
}
買賣股票問題
ds_74
121. 買賣股票的最佳時機（easy）限定交易次數 k=1
122. 買賣股票的最佳時機 II（medium）交易次數無限制 k = +infinity
123. 買賣股票的最佳時機 III (hrad) 限定交易次數 k=2
188. 買賣股票的最佳時機 IV (hard) 限定交易次數 最多次數為 k
309. 最佳買賣股票時機含冷凍期(medium) 含有交易冷凍期
714. 買賣股票的最佳時機含手續(xù)費 (medium) 每次交易含手續(xù)費
第5圃庭，6道題相當于在第2道題的基礎上加了冷凍期和手續(xù)費的條件。
限制條件
- 先買入才能賣出
- 不能同時參加多筆交易失晴，再次買入時剧腻，需要先賣出
-
k >= 0才能進行交易，否則沒有交易次數
定義操作
- 買入
- 賣出
- 不操作
定義狀態(tài)
-
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]，因為最后一天賣出肯定比持有收益更高
狀態(tài)轉移方程
// 今天沒有持有股票拆又，分為兩種情況
// 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
狀態(tài)轉移方程
//第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];
};
狀態(tài)壓縮调俘，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
狀態(tài)轉移方程
//第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];
};
狀態(tài)壓縮彩库，同樣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
狀態(tài)轉移方程
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進行循環(huán)
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骇钦，直接寫出循環(huán)的結果
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
const maxProfit = function (k, prices) {
let n = prices.length;
let profit = new Array(k);//和123題一樣 求出所有k的狀態(tài)
// 初始化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循環(huán)就可以
//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) 含有交易冷凍期
狀態(tài)轉移方程
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
//冷卻時間1天，所以要從 i - 2 天轉移狀態(tài)
//買入鳞仙，賣出 ---- 冷凍期 ---- 買入寇蚊，賣出
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. 買賣股票的最佳時機含手續(xù)費 (medium) 每次交易含手續(xù)費
狀態(tài)轉移方程
//每次交易要支付手續(xù)費 我們定義在賣出的時候扣手續(xù)費
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;
};
322. 零錢兌換 (medium)
ds_75
不能用貪心做棍好，反例仗岸，coins=[1, 3, 5, 6, 7]，amount=30借笙，用貪心先用最大的面額7扒怖，在用2個1，4 * 7 + 2 * 1 = 30提澎，但是我們用5個6姚垃，5 * 6 = 30 就能用最少的硬幣兌換完成
方法1.動態(tài)規(guī)劃
- 思路：
dp[i]表示兌換面額i所需要的最少硬幣念链，因為硬幣無限盼忌，所以可以自底向上計算dp[i]，對于dp[0~i]的每個狀態(tài)掂墓，循環(huán)coins數組谦纱，尋找可以兌換的組合，用i面額減去當前硬幣價值君编，dp[i-coin]在加上一個硬幣數就是dp[i],最后取最小值就是答案跨嘉，狀態(tài)轉移方程就是dp[i] = Math.min(dp[i], dp[i - coin] + 1); - 復雜度分析：時間復雜度是O(sn)，s是兌換金額吃嘿，n是硬幣數組長度祠乃，一共需要計算s個狀態(tài)，每個狀態(tài)需要遍歷n個面額來轉移狀態(tài)兑燥×链桑空間復雜度是
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++) {//循環(huán)面額
for (let coin of coins) {//循環(huán)硬幣數組
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降瞳，則無法兌換
};
Java:
public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
72. 編輯距離 （hard）
方法1.動態(tài)規(guī)劃
ds_76
ds_77
- 思路：
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刪除最后一個字符沛膳，狀態(tài)轉移成
dp[i-1][j]，即dp[i][j] = dp[i-1][j] + 1汛聚，+1指刪除操作 - word1在最后加上一個字符锹安，狀態(tài)轉移成
dp[i][j-1]，即dp[i][j] = dp[i][j-1] + 1倚舀，+1指增加操作 - word1替換最后一個字符八毯，狀態(tài)轉移成
dp[i-1][j-1]，即dp[i] [j] = dp[i-1] [j-1] + 1瞄桨，+1指替換操作
- word1刪除最后一個字符沛膳，狀態(tài)轉移成
- 如果
- 復雜度：時間復雜度是
O(mn)话速，m是word1的長度，n是word2的長度芯侥〔唇唬空間復雜度是O(mn)，需要用m * n大小的二維數字存儲狀態(tài)柱查。
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++) {
//循環(huán)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];
};
Java:
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
}
}
}
return dp[m][n];
}
