一些分析總結(jié)
01 背包 問題和 完全背包 問題的不同點在于，所有的物品只能使用一次，判斷?哪些物品?裝進(jìn)背包里 物品價值和 最大；而 完全背包 問題中，所有物品都能使用n次，判斷 哪個物品 裝 n 個進(jìn)去 物品價值和 最大。
01 背包的遞推公式是：【當(dāng)然先遍歷物品還是背包的容量都可以】
for(var i = 0; i < nums.length; i++) {
for(var j = target; j <= nums[i]; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
}
}還有一種就是 一維滾動數(shù)組，原本的?二維數(shù)組 dp[i][j] 表示第 i 層、背包容量為 j 時的狀態(tài)值，而遞推中 只需要用到上一層的狀態(tài) dp[i-1][j] 和 dp[i-1][j-weight[i]]。因此，可以通過在一維數(shù)組中使用滾動的方式，將上一層的狀態(tài)直接拷貝到當(dāng)前層，從而節(jié)省空間。這種優(yōu)化僅適用于無需回溯到更早層次，只需要關(guān)注前一層狀態(tài)的情況。
for(var i = 0; i < nums.length; i++) {
for(var j = target; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + value[i]);
}
}這里的內(nèi)層循環(huán)采用了倒序遍歷，dp[j] 表示遍歷到第 i 個物品、背包容量為 j 時的最優(yōu)解。倒序遍歷可以確保在計算 dp[j] 時，dp[j - weight[i]] 仍然表示第 i-1 個物品、背包容量為 j-weight[i] 時的最優(yōu)解，不會受到當(dāng)前層的狀態(tài)更新影響。
接下來就是這篇文章的重頭戲，完全背包 問題：每種物品都有無限件可供選擇，求在有限的背包容量下，如何選擇物品價值和最大化。
1.首先就是確立狀態(tài)：dp[i][j] 表示前 i 個物品，背包容量為 j 時的最大價值。
對于第 i 個物品，可選放入多個此它，直到超過背包容量。 對于每個物品，要么放入，要么不放。
如果選擇放入，剩余的背包容量就變成?j - weight[i]。 在放入一個物品后，變?yōu)榍笄?i 個物品，背包容量為 j - weight[i] 的最大價值，即 dp[i][j - weight[i]]。
如果選擇不放入，變?yōu)榍笄?i-1 個物品，背包容量為 j 的最大價值，即 dp[i-1][j]。
因此遞推公式為：
for(let j = 0; j <= bagWeight; j++) {
for(let i = 0; i < nums.length; i++) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + value[i])
}
}OR?
for(let i = 0; i < nums.length; i++) {
for(let j = nums[i]; i <= bagWeight; j++) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + value[i])
}
}此處的兩層循環(huán)可以顛倒：
按照?外層循環(huán)是物品，內(nèi)層循環(huán)是背包容量?的遍歷方式時，如果當(dāng)前物品 i 的重量 weight[i] 較小，在更新 dp[j] 的過程中，將會使用到同一層之前已經(jīng)更新過的狀態(tài)值 dp[j - weight[i]]。 由于?完全背包問題 每個物品可以選擇多次，在計算 dp[j - weight[i]] 時，確保計算了當(dāng)前物品 i ，得到?dp[j - weight[i] + value[i]]。在計算 dp[j] 時，如果再使用 dp[j - weight[i]] 進(jìn)行更新，相當(dāng)于將物品 i 又選一次，這樣就允許了重復(fù)選擇相同物品的情況。
進(jìn)入正題?
518. 零錢兌換 II
給你一個整數(shù)數(shù)組 coins 表示不同面額的硬幣，另給一個整數(shù) amount 表示總金額。
請你計算并返回可以湊成總金額的硬幣組合數(shù)。如果任何硬幣組合都無法湊出總金額，返回 0 。
假設(shè)每一種面額的硬幣有無限個。?
題目數(shù)據(jù)保證結(jié)果符合 32 位帶符號整數(shù)。
鏈接：力扣
解題思路：
這道題是完全背包問題，但也涉及到排列組合的問題，因為 5=2+2+1 和 5=2+1+2 是兩種組合方式，但我們這里只需要?組合方式?即可，上面說到完全背包問題的兩層循環(huán)是可以顛倒的，但本題很特殊，如果進(jìn)行了顛倒會怎么樣，下面進(jìn)行分析：
假如輸入是 amount = 6, coins = [1, 5]
// 先遍歷物品
for (let i = 0; i < coins.size(); i++) {
// 再遍歷背包容量
for (let j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]]
}
}執(zhí)行順序：
外層循環(huán)遍歷物品：
- 從 i = 0 開始，遍歷每個物品
coins.size()?表示物品的數(shù)量，coins[i]?表示第 i 個物品的價值內(nèi)層循環(huán)遍歷背包容量：
- 從 j = coins[i] 開始，直到超過目標(biāo)容量?
amountdp[j] += dp[j - coins[i]]?表示更新當(dāng)前背包容量 j 下的最優(yōu)解，將之前計算過的狀態(tài)值?dp[j - coins[i]]?加上當(dāng)前物品的價值，即選擇第 i 個物品的情況通過依次遍歷每個物品和背包容量，不斷更新最優(yōu)解，最終得到完全背包問題的最優(yōu)解
先將 1 加入計算，再計算 5，得到的方法只有 {1, 5}，沒有 {5, 1}，得到了組合數(shù)是?1
如果將兩層循環(huán)進(jìn)行顛倒：
// 先遍歷背包容量
for (let j = 0; j <= amount; j++) {
// 再遍歷物品
for (let i = 0; i < coins.length; i++) {
dp[j] += dp[j - coins[i]]
}
}執(zhí)行順序：
- 外層循環(huán)遍歷背包容量，從0到金額?
amount- 內(nèi)層循環(huán)遍歷物品
- 在內(nèi)循環(huán)中，對于每個背包容量?
j，通過累加計算湊成金額?j?的組合數(shù)量
- 逐個考慮當(dāng)前物品的面額?
coins[i]- 如果?
j - coins[i]?>= 0，表示可以選擇當(dāng)前物品，將其加入組合中- 更新狀態(tài)轉(zhuǎn)移方程?
dp[j] += dp[j - coins[i]]，將前面計算得到的組合數(shù)量加到當(dāng)前容量為?j?的組合數(shù)中- 完成內(nèi)層循環(huán)后，外層循環(huán)繼續(xù)下一個背包容量的遍歷
- 最終得到的數(shù)組?
dp?中的元素?dp[amount]?即為湊成目標(biāo)金額?amount?的組合數(shù)量背包容量的每個值，都經(jīng)過 1 和 5 ，包含了 {1, 5} 和 {5, 1} 兩種情況，得到了排列數(shù)是 2
因此只能先遍歷物品再遍歷背包容量，完整代碼如下：
var change = function(amount, coins) {
// 如果這一個硬幣等于 總金額，直接返回1
if(coins.length == 1 && coins[0] == amount) return 1
let 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]
}377. 組合總和 Ⅳ
給你一個由 不同 整數(shù)組成的數(shù)組 nums ，和一個目標(biāo)整數(shù) target 。請你從 nums 中找出并返回總和為 target 的元素組合的個數(shù)。
題目數(shù)據(jù)保證答案符合 32 位整數(shù)范圍。
鏈接：力扣
解題思路：
本題就是區(qū)別于上題所說的，用到了排列的方式，以下是完整代碼：?
var combinationSum4 = function(nums, target) {
// 如果這一個元素等于 target ，直接返回1
if(nums.length == 1) {
if(nums[0] == target) return 1
else if(nums[0] > target) return 0
}
let dp = Array(target + 1).fill(0)
dp[0] = 1
for(let j = 0; j <= target; j++) {
for(let i = 0; i < nums.length; i++) {
// 如果背包容量是大于當(dāng)前元素的才能進(jìn)行計算，不然裝不下
if(j >= nums[i]) dp[j] += dp[j - nums[i]]
}
}
return dp[target]
}70. 爬樓梯
假設(shè)你正在爬樓梯。需要?n?階你才能到達(dá)樓頂。
每次你可以爬?1?或?2?個臺階。你有多少種不同的方法可以爬到樓頂呢？
鏈接：力扣
var climbStairs = function(n) {
const dp = [1, 2]
for(let i = 2; i < n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n-1]
}322. 零錢兌換
給你一個整數(shù)數(shù)組 coins ，表示不同面額的硬幣；以及一個整數(shù) amount ，表示總金額。
計算并返回可以湊成總金額所需的 最少的硬幣個數(shù) 。如果沒有任何一種硬幣組合能組成總金額，返回?-1 。
你可以認(rèn)為每種硬幣的數(shù)量是無限的
鏈接：力扣
外層循環(huán)遍歷每種硬幣，內(nèi)層循環(huán)從當(dāng)前硬幣的面值開始，到目標(biāo)金額結(jié)束，逐個更新
dp數(shù)組。對于每個金額j，將其更新為?dp[j-coins[i]] + 1?與原來的?dp[j]?之間的較小值，其中?coins[i]?表示當(dāng)前硬幣面值。最后，函數(shù)返回?
dp[amount]?的值，如果?dp[amount]?仍為無窮大，則說明無法湊成目標(biāo)金額，返回-1；否則返回最少所需硬幣數(shù)量。
var coinChange = function(coins, amount) {
if(amount == 0) return 0
if(coins.length == 1 && coins[0] > amount) return -1
let dp = Array(amount + 1).fill(Infinity)
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 - coins[i]] + 1, dp[j])
}
}
return dp[amount] === Infinity ? -1 : dp[amount]
}279. 完全平方數(shù)
給你一個整數(shù) n ，返回 和為 n 的完全平方數(shù)的最少數(shù)量 。
完全平方數(shù) 是一個整數(shù)，其值等于另一個整數(shù)的平方；換句話說，其值等于一個整數(shù)自乘的積。例如，1、4、9 和 16 都是完全平方數(shù)，而 3 和 11 不是。
鏈接：力扣
- 使用兩層循環(huán)來遍歷完全平方數(shù)。外層循環(huán)從1開始逐個取平方根，直到平方值 <= n
- 內(nèi)層循環(huán)從當(dāng)前完全平方數(shù)開始，到目標(biāo)數(shù)n結(jié)束，逐個更新
dp數(shù)組。對于每個數(shù)j，將其更新為?dp[j-val] + 1?與原來的?dp[j]?之間的較小值，其中val表示當(dāng)前完全平方數(shù)的值
var numSquares = function(n) {
let dp = Array(n + 1).fill(Infinity)
dp[0] = 0
for(let i =1; i ** 2 <= n; i++) {
let val = i ** 2
for(let j = val; j <= n; j++) {
dp[j] = Math.min(dp[j - val] + 1, dp[j])
}
}
return dp[n]
}139. 單詞拆分
給你一個字符串 s 和一個字符串列表 wordDict 作為字典。請你判斷是否可以利用字典中出現(xiàn)的單詞拼接出 s 。
注意：不要求字典中出現(xiàn)的單詞全部都使用，并且字典中的單詞可以重復(fù)使用。
鏈接：力扣
var wordBreak = function(s, wordDict) {
let dp = Array(s.length + 1).fill(false)
dp[0] = true
// 排列問題，先遍歷背包容量，再遍歷物品
for(let i = 0; i <= s.length; i++){
for(let j = 0; j < wordDict.length; j++) {
if(i >= wordDict[j].length) {
if(s.slice(i - wordDict[j].length, i) === wordDict[j] && dp[i - wordDict[j].length]) dp[i] = true
}
}
}
return dp[s.length]
}198. 打家劫舍
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組，計算你 不觸動警報裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。
鏈接：力扣
解題思路：
“如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警”，則當(dāng)我偷第 i? 間房時，就不考慮 第 i-1 間，然后去偷 i+2 間房，反之就是偷 i-1 間房。?并且dp[0] 定是 nums[0]，dp[1] 是max(nums[0], nums[1])，來決定我以何種間隔進(jìn)行計算。
var rob = function(nums) {
if(nums.length == 0) return 0
const dp = [nums[0], Math.max(nums[0], nums[1])]
for(let i = 2; i < nums.length; i++) {
// 錯位相加
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
}
return dp[nums.length - 1]
}213. 打家劫舍 II
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金。這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警 。
給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。
鏈接：力扣
解題思路：
此題和上一題的不同之處就是成了環(huán)，在原有的相鄰的不能偷的基礎(chǔ)上，需要考慮情況偷了 nums[1] 就不能偷 nums[nums.length - 1]，這就是區(qū)別。
var rob = function(nums) {
if(nums.length == 1) return nums[0]
let res1 = toRob(nums, 0, nums.length - 2)
let res2 = toRob(nums, 1, nums.length - 1)
return Math.max(res1, res2)
}
var toRob = function(nums, start, end) {
// 如果首尾相同，偷一個
if(start == end) return nums[start]
const dp = Array(nums.length).fill(0)
// 從第一個開始
dp[start] = nums[start]
// 選擇偷第一個房或第二個房
dp[start+1] = Math.max(nums[start], nums[start+1])
for(let i = start + 2; i <= end; i++) {
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1])
}
return dp[end]
}337. 打家劫舍 III
小偷又發(fā)現(xiàn)了一個新的可行竊的地區(qū)。這個地區(qū)只有一個入口，我們稱之為?root?。
除了?root?之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。 如果 兩個直接相連的房子在同一天晚上被打劫 ，房屋將自動報警。
給定二叉樹的?root?。返回?在不觸動警報的情況下?，小偷能夠盜取的最高金額?。
鏈接：力扣
解題思路：
通過使用一個長度為2的數(shù)組的狀態(tài)轉(zhuǎn)移方程，來記錄狀態(tài)變化，記錄當(dāng)前節(jié)點選擇偷還是不偷所得到的最大金額，并且將其結(jié)果存儲在哈希表中，避免了重復(fù)遍歷。
需要分別計算不偷當(dāng)前節(jié)點和偷當(dāng)前節(jié)點的最大金額：
- 不偷當(dāng)前節(jié)點時，可以選擇偷或不偷左子節(jié)點，偷或不偷右子節(jié)點，取兩者之間最大值，保存在變量?
Not?中- 偷當(dāng)前節(jié)點時，不能偷其左右子節(jié)點，將當(dāng)前節(jié)點的值 與 左子節(jié)點不偷的最大金額 與 右子節(jié)點不偷的最大金額 相加，保存在變量?
Do?中
const rob = function(root) {
// 通過哈希表保存已計算過的節(jié)點的結(jié)果
const map = new Map()
// 后序遍歷函數(shù)
const postOrderTraversal = function(node) {
// 遞歸出口
if (!node) return [0, 0]
// 避免重復(fù)遍歷
if(map.has(node)) return map.get(node)
// 遍歷子樹
const left = postOrderTraversal(node.left)
const right = postOrderTraversal(node.right)
// 不偷當(dāng)前節(jié)點，其左右子節(jié)點可以偷或不偷，取最大值
const Not = Math.max(left[0], left[1]) + Math.max(right[0], right[1])
// 偷當(dāng)前節(jié)點，左右子節(jié)點只能不偷
const Do = node.val + left[0] + right[0]
// 返回選擇偷還是不偷
const result = [Not, Do]
map.set(node, result)
return result
}
const res = postOrderTraversal(root)
// 返回最大值
return Math.max(...res)
}121. 買賣股票的最佳時機(jī)
給定一個數(shù)組 prices ，它的第?i 個元素?prices[i] 表示一支給定股票第 i 天的價格。
你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票。設(shè)計一個算法來計算你所能獲取的最大利潤。
返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。
鏈接：力扣
解題思路：
dp[i]?表示第?i?天結(jié)束后的狀態(tài)，每個狀態(tài)由兩個值組成：dp[i][0]?表示持有股票時的最大利潤，dp[i][1]?表示不持有股票時的最大利潤- 初始化第一天的狀態(tài)為?
[-prices[0], 0]，即第一天選擇買入股票，沒有賣出- 從第二天開始遍歷價格數(shù)組，對于每一天?
i：
dp[i][0]?的取值為?前一天持有股票的最大利潤?與?當(dāng)天買入股票后的利潤?中的較大值，即?Math.max(dp[i - 1][0], -prices[i])。表示選擇 保持前一天的股票狀態(tài) 或 將前一天 不持有股票 的狀態(tài)轉(zhuǎn)變?yōu)?持有股票 的狀態(tài)dp[i][1]?的取值為 前一天不持有股票的最大利潤 與 當(dāng)天賣出股票后的利潤 中的較大值，即?Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0])。表示選擇 保持前一天的股票狀態(tài) 或 將前一天持有股票 的狀態(tài)轉(zhuǎn)變?yōu)?不持有股票 的狀態(tài)，并獲得當(dāng)天的賣出利潤- 最終結(jié)果為?
dp[len - 1][1]，表示最后一天不持有股票時的最大利潤
貪心算法：?
var maxProfit = function(prices) {
if(prices.length == 1) return 0
let min = prices[0], max = 0
for(let i = 0; i < prices.length; i++) {
// 前一天的差值和今天賣出的差值
max = Math.max(max, prices[i] - min)
// 之前買入的價格和今天買入的價格
min = Math.min(min, prices[i])
}
return max
}動態(tài)規(guī)劃：
var maxProfit = function(prices) {
const len = prices.length
// 創(chuàng)建dp數(shù)組
const dp = new Array(len).fill([0, 0])
// dp 數(shù)組初始化
dp[0] = [-prices[0], 0]
for (let i = 1; i < len; i++) {
// 更新dp[i]
dp[i] = [
// 前一天持有股票的最大利潤?與?當(dāng)天買入股票后的利潤 的最大值
Math.max(dp[i - 1][0], -prices[i]),
// 前一天不持有股票的最大利潤 與 當(dāng)天賣出股票后的利潤 的最大值
Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]),
]
}
return dp[len - 1][1]
}122. 買賣股票的最佳時機(jī) II
給你一個整數(shù)數(shù)組 prices ，其中?prices[i] 表示某支股票第 i 天的價格。
在每一天，你可以決定是否購買和/或出售股票。你在任何時候?最多?只能持有 一股 股票。你也可以先購買，然后在 同一天 出售。
返回 你能獲得的 最大 利潤?。
鏈接：力扣
本題和上一題的不同之處在于：
- 上一題股票只能買賣一次，如果買入股票，那么第 i 天持有股票，即 dp[i][0] 是?-prices[i]
- 本題一只股票可以買賣多次，當(dāng)?shù)?i 天買入股票時，持有的現(xiàn)金可能有之前產(chǎn)生的利潤
- 第 i 天持有股票即 dp[i][0]，如果第 i 天買入股票，所得現(xiàn)金是 昨天不持有股票的所得現(xiàn)金 減去 今天的股票價格，即 dp[i - 1][1] - prices[i]
貪心算法：?
var maxProfit = function(prices) {
var res = 0
// 計算正利潤
var odd = 0
for(var i = prices.length-1; i >= 0; i--) {
// 進(jìn)行差值計算
odd = prices[i] - prices[i-1]
// 如果是正利潤就放入結(jié)果中
if(odd > 0) res += odd
else odd = 0
}
return res
}動態(tài)規(guī)劃：
var maxProfit = function(prices) {
const len = prices.length
let dp = Array.from(Array(len).fill(0))
dp[0] = [-prices[0], 0]
for(let i = 1; i < len; i++) {
dp[i] = [
// dp[i-1][1] - prices[i] = 不持有的利潤 減去 買入的價格
Math.max(dp[i-1][0], dp[i-1][1] - prices[i]),
Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
]
}
return dp[len -1][1]
}123. 買賣股票的最佳時機(jī) III
給定一個數(shù)組，它的第 i 個元素是一支給定的股票在第 i 天的價格。
設(shè)計一個算法來計算你所能獲取的最大利潤。你最多可以完成?兩筆?交易。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
鏈接：力扣
解題思路：
這一題相較于上面兩題，不同之處在于，只能進(jìn)行兩次交易，因此我們需要考慮：
何時第一次買入，何時第一次賣出
何時第二次買入，何時第二次賣出
代碼不同的地方就是遞推公式需要判斷 買入時的利潤 和 賣出的利潤 是基于第幾次?
var maxProfit = function(prices) {
const len = prices.length
let dp = Array.from(Array(len).fill(0))
dp[0] = [-prices[0], 0, -prices[0], 0]
for(let i = 1; i < len; i++) {
dp[i] = [
Math.max(dp[i-1][0], -prices[i]),
Math.max(dp[i-1][1], dp[i-1][0] + prices[i]),
Math.max(dp[i-1][2], dp[i-1][1] - prices[i]),
Math.max(dp[i-1][3], dp[i-1][2] + prices[i])
]
}
return dp[len -1][3]
}188. 買賣股票的最佳時機(jī) IV
給定一個整數(shù)數(shù)組?prices ，它的第 i 個元素?prices[i] 是一支給定的股票在第 i 天的價格，和一個整型 k 。設(shè)計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。也就是說，你最多可以買 k 次，賣 k 次。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
鏈接：力扣
解題思路：
基于上面一題的思路，我們不可能將k次全部列出，但賣出之前必須買入，可得，奇數(shù)時買入，偶數(shù)時賣出
- 初始化第一天的狀態(tài)，對于奇數(shù)索引?
j，即買入狀態(tài)，將其設(shè)置為?0 - prices[0]，表示第一天進(jìn)行買入操作得到的利潤- 從第二天開始遍歷價格數(shù)組，對于每一天?
i?和交易次數(shù)索引?j（從0開始，以2遞增）- 更新?
dp[i][j+1]，表示第?i?天結(jié)束后進(jìn)行?j+1?次交易時 持有股票的最大利潤。取 前一天持有股票的最大利潤?dp[i-1][j+1]?和 前一天不持有股票的最大利潤 加 當(dāng)天買入股票后的利潤 的較大值
var maxProfit = function(k, prices) {
const len = prices.length
// 行數(shù) prices.length，列數(shù) 2 * k + 1
let dp = Array.from(Array(prices.length), () => Array(2*k+1).fill(0))
// 第一天買入時得到的利潤
for(let i = 1; i < 2 * k; i += 2) {
dp[0][i] = -prices[0]
}
for(let i = 1; i < len; i++) {
for (let j = 0; j < 2 * k; j += 2) {
dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] - prices[i]);
dp[i][j+2] = Math.max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]);
}
}
return dp[len - 1][2 * k]
}309. 最佳買賣股票時機(jī)含冷凍期
給定一個整數(shù)數(shù)組prices，其中第??prices[i]?表示第?i?天的股票價格 。?
設(shè)計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
鏈接：力扣
?
dp[i][0]：表示第?i?天結(jié)束時持有股票的最大利潤
dp[i][1]：表示第?i?天結(jié)束時不持有股票且處于冷凍期的最大利潤
dp[i][2]：表示第?i?天結(jié)束時不持有股票且不處于冷凍期的最大利潤
var maxProfit = function(prices) {
const len = prices.length
let dp = Array.from(Array(len), () => Array(3).fill(0))
dp[0][0] = -prices[0]
for (let i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][0])
dp[i][1] = dp[i - 1][0] + prices[i]
dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2])
}
return Math.max(dp[len - 1][1], dp[len - 1][2])
}714. 買賣股票的最佳時機(jī)含手續(xù)費
給定一個整數(shù)數(shù)組?prices，其中 prices[i]表示第?i?天的股票價格 ；整數(shù)?fee 代表了交易股票的手續(xù)費用。
你可以無限次地完成交易，但是你每筆交易都需要付手續(xù)費。如果你已經(jīng)購買了一個股票，在賣出它之前你就不能再繼續(xù)購買股票了。
返回獲得利潤的最大值。
注意：這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續(xù)費。
鏈接：力扣文章來源：http://www.zghlxwxcb.cn/news/detail-712418.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-712418.html
var maxProfit = function(prices, fee) {
const len = prices.length
let dp = Array.from(Array(len).fill(0))
dp[0] = [-prices[0], 0]
for(let i = 1; i < len; i++) {
dp[i] = [
Math.max(dp[i-1][0], dp[i-1][1] - prices[i]),
Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
]
}
return dp[len -1][1]
}到了這里，關(guān)于算法篇——動態(tài)規(guī)劃 完全和多重背包問題 (js版)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
