leetcode—動態規劃-揹包問題
動規以空間換取時間
動態規劃刷題總結以下型別及leetcode題目：
揹包
416 分割等和子集（medium）
494 目標和（medium）
474 一和零（medium）
322 零錢兌換（medium）
518 零錢兌換 II（medium）
139 單詞拆分（medium）
377 組合總和 Ⅳ（medium）
1維寫法簡單總結
1。如果是0-1揹包，即陣列中的元素不可重複使用，nums放在外迴圈，target在內迴圈，且內迴圈倒序；
for num in nums：
for i in range（target， num-1， -1）：
2。如果是完全揹包，即陣列中的元素可重複使用，nums放在外迴圈，target在內迴圈。且內迴圈正序。
for num in nums：
for i in range（num， target+1）：
3。如果組合問題需考慮元素之間的順序，需將target放在外迴圈，將nums放在內迴圈。
for i in range（1， target+1）：
for num in nums：
揹包問題
416 分割等和子集（medium）
https：//
leetcode-cn。com/problem
s/partition-equal-subset-sum/
動規（空間未最佳化）
class
Solution
：
def
canPartition
（
self
，
nums
：
List
［
int
］）
->
bool
：
# 將揹包容量看作sum的一半
if
not
nums
：
return
False
sum_
=
sum
（
nums
）
if
sum_
%
2
！=
0
：
return
False
target
=
sum_
//
2
# 有n個物品，容量為target，每個物品的價值與物品的重量一樣
dp
=
［［
-
1
for
_
in
range
（
target
+
1
）］
for
_
in
range
（
len
（
nums
））］
# 先初始化第一行（將第零個物品裝入內部）
for
i
in
range
（
target
+
1
）：
dp
［
0
］［
i
］
=
nums
［
0
］
if
nums
［
0
］
<=
i
else
0
#處理dp表的後邊幾行
for
i
in
range
（
1
，
len
（
nums
））：
for
j
in
range
（
target
+
1
）：
# 不放置第i個物品
dp
［
i
］［
j
］
=
dp
［
i
-
1
］［
j
］
if
nums
［
i
］
<=
j
：
dp
［
i
］［
j
］
=
max
（
dp
［
i
］［
j
］，
nums
［
i
］
+
dp
［
i
-
1
］［
j
-
nums
［
i
］］）
# print（dp）
return
dp
［
-
1
］［
-
1
］
==
target
空間最佳化動規
class
Solution
：
def
canPartition
（
self
，
nums
：
List
［
int
］）
->
bool
：
# 將揹包容量看作sum的一半
if
not
nums
：
return
False
sum_
=
sum
（
nums
）
if
sum_
%
2
！=
0
：
return
False
target
=
sum_
//
2
# 有n個物品，容量為target，每個物品的價值與物品的重量一樣
# 實際上狀態僅僅與上一行的狀態有關，因此只需要維持兩行的空間即可
dp
=
［［
-
1
for
_
in
range
（
target
+
1
）］
for
_
in
range
（
2
）］
# 先初始化第一行（將第零個物品裝入內部）
for
i
in
range
（
target
+
1
）：
dp
［
0
］［
i
］
=
nums
［
0
］
if
nums
［
0
］
<=
i
else
0
#處理dp表的後邊幾行，僅僅維持兩行，可以將偶數行放置在dp表的第0行，奇數行放置在dp表的第1行
for
i
in
range
（
1
，
len
（
nums
））：
for
j
in
range
（
target
+
1
）：
# 不放置第i個物品
dp
［
i
%
2
］［
j
］
=
dp
［（
i
-
1
）
%
2
］［
j
］
if
nums
［
i
］
<=
j
：
dp
［
i
%
2
］［
j
］
=
max
（
dp
［
i
%
2
］［
j
］，
nums
［
i
］
+
dp
［（
i
-
1
）
%
2
］［
j
-
nums
［
i
］］）
# print（dp）
return
dp
［（
len
（
nums
）
-
1
）
%
2
］［
-
1
］
==
target
class
Solution
：
def
canPartition
（
self
，
nums
：
List
［
int
］）
->
bool
：
‘’‘
01揹包
1維寫法
’‘’
if
not
nums
：
return
True
sum_
=
sum
（
nums
）
if
sum_
&
1
：
return
False
target
=
sum_
//
2
dp
=
［
0
for
_
in
range
（
target
+
1
）］
for
i
in
range
（
target
+
1
）：
if
nums
［
0
］
<=
i
：
dp
［
i
］
=
nums
［
0
］
for
num
in
nums
［
1
：］：
## 01揹包問題倒序，這裡不採用遍歷到0，因為揹包容量小於num，裝不進去，提前終止
for
i
in
range
（
target
，
num
-
1
，
-
1
）：
dp
［
i
］
=
max
（
dp
［
i
］，
dp
［
i
-
num
］
+
num
）
# print（dp）
return
dp
［
-
1
］
==
target
494 目標和（medium）
https：//
leetcode-cn。com/problem
s/target-sum/
class
Solution
：
def
findTargetSumWays
（
self
，
nums
：
List
［
int
］，
S
：
int
）
->
int
：
‘’‘
01揹包問題：target為計算後的target，找子序列和為target的個數
揹包容量為target，物品重量為元素的值
dp［i］［j］ i為考慮前i個元素，j為容量，dp［i］［j］表示目標和為j的方法數
狀態轉移方程為：dp［i］［j］ = dp［i-1］［j］ + dp［i-1］［j-nums［i］］
’‘’
x
=
sum
（
nums
）
if
x
<
S
：
return
0
tm
=
x
+
S
if
tm
&
1
：
return
0
target
=
int
（（
tm
）
/
2
）
dp
=
［［
0
for
_
in
range
（
target
+
1
）］
for
_
in
range
（
len
（
nums
）
+
1
）］
dp
［
0
］［
0
］
=
1
for
i
in
range
（
1
，
len
（
nums
）
+
1
）：
for
j
in
range
（
target
+
1
）：
if
j
>=
nums
［
i
-
1
］：
dp
［
i
］［
j
］
=
dp
［
i
-
1
］［
j
］
+
dp
［
i
-
1
］［
j
-
nums
［
i
-
1
］］
else
：
dp
［
i
］［
j
］
=
dp
［
i
-
1
］［
j
］
# print（dp）
return
dp
［
-
1
］［
-
1
］
class
Solution
：
def
findTargetSumWays
（
self
，
nums
：
List
［
int
］，
S
：
int
）
->
int
：
‘’‘
01揹包問題 1維寫法
sum（P） - sum（N） = target
sum（P） + sum（N） + sum（P） - sum（N） = target + sum（P） + sum（N）
2 * sum（P） = target + sum（nums）
target為計算後的target，找子序列和為target的個數
’‘’
x
=
sum
（
nums
）
if
x
<
S
：
return
0
tm
=
x
+
S
if
tm
&
1
：
return
0
target
=
int
（（
tm
）
/
2
）
dp
=
［
0
for
_
in
range
（
target
+
1
）］
dp
［
0
］
=
1
for
num
in
nums
：
for
j
in
range
（
target
，
num
-
1
，
-
1
）：
dp
［
j
］
+=
dp
［
j
-
num
］
# print（dp）
return
dp
［
-
1
］
474 一和零（medium）
https：//
leetcode-cn。com/problem
s/ones-and-zeroes/
思路：等同於416題的思路
class
Solution
：
def
findMaxForm
（
self
，
strs
：
List
［
str
］，
m
：
int
，
n
：
int
）
->
int
：
‘’‘
轉換為0 1揹包問題
dp［i］［j］［k］， j為0的容量， k為1的容量，i為裝入字串的個數，字串相當於物品，價值為1
分兩種情況，第一將第i個字串加入揹包，此時，dp［i］［j］［k］ = dp［i-1］［j-0的使用個數］［k-1的使用個數］+1
第二種，不將第i個字串加入揹包，此使dp［i］［j］［k］ = dp［i-1］［j］［k］
’‘’
dp
=
［［［
0
for
_
in
range
（
n
+
1
）］
for
_
in
range
（
m
+
1
）］
for
_
in
range
（
len
（
strs
））］
one
=
strs
［
0
］
。
count
（
‘1’
）
zero
=
strs
［
0
］
。
count
（
‘0’
）
for
i
in
range
（
m
+
1
）：
for
j
in
range
（
n
+
1
）：
if
i
>=
zero
and
j
>=
one
：
dp
［
0
］［
i
］［
j
］
=
1
for
i
in
range
（
1
，
len
（
strs
））：
one
=
strs
［
i
］
。
count
（
‘1’
）
zero
=
strs
［
i
］
。
count
（
‘0’
）
for
j
in
range
（
m
+
1
）：
for
k
in
range
（
n
+
1
）：
dp
［
i
］［
j
］［
k
］
=
dp
［
i
-
1
］［
j
］［
k
］
if
j
>=
zero
and
k
>=
one
：
dp
［
i
］［
j
］［
k
］
=
max
（
dp
［
i
］［
j
］［
k
］，
dp
［
i
-
1
］［
j
-
zero
］［
k
-
one
］
+
1
）
# print（dp）
return
dp
［
-
1
］［
-
1
］［
-
1
］
class
Solution
：
def
findMaxForm
（
self
，
strs
：
List
［
str
］，
m
：
int
，
n
：
int
）
->
int
：
‘’‘
轉換為0 1揹包問題 2維寫法（類似於1維寫法）
’‘’
dp
=
［［
0
for
_
in
range
（
n
+
1
）］
for
_
in
range
（
m
+
1
）］
one
=
strs
［
0
］
。
count
（
‘1’
）
zero
=
strs
［
0
］
。
count
（
‘0’
）
for
i
in
range
（
m
+
1
）：
for
j
in
range
（
n
+
1
）：
if
i
>=
zero
and
j
>=
one
：
dp
［
i
］［
j
］
=
1
for
i
in
range
（
1
，
len
（
strs
））：
one
=
strs
［
i
］
。
count
（
‘1’
）
zero
=
strs
［
i
］
。
count
（
‘0’
）
for
j
in
range
（
m
，
zero
-
1
，
-
1
）：
for
k
in
range
（
n
，
one
-
1
，
-
1
）：
dp
［
j
］［
k
］
=
max
（
dp
［
j
］［
k
］，
dp
［
j
-
zero
］［
k
-
one
］
+
1
）
# print（dp）
return
dp
［
-
1
］［
-
1
］
322 零錢兌換（medium）
https：//
leetcode-cn。com/problem
s/coin-change/
class
Solution
：
def
coinChange
（
self
，
coins
：
List
［
int
］，
amount
：
int
）
->
int
：
‘’‘
完全揹包問題，揹包的容量為amount，物品的重量為coins的面額
硬幣的個數無限。
剛好裝滿揹包硬幣數目最少。
dp［i］［j］表示前i種硬幣，組合成j的最小的硬幣個數
狀態轉移：
對於第i種硬幣，選擇不拿，或者拿1到k個，其中最小的值
dp［i］［j］ = min（dp［i-1］［j］， dp［i-1］［j-c］+1， dp［i-1］［j-2*c］+2， 。。。，dp［i-1］［j-c*k］+k）
同時，對於dp［i］［j-c］= min（dp［i-1］［j-c］， dp［i-1］［j-c*2］+1， dp［i-1］［j-c*k］+k-1）
因此去掉冗餘的計算
dp［i］［j］ = min（dp［i-1］［j］， dp［i］［j-c］+1）
’‘’
dp
=
［［
float
（
‘inf’
）
for
_
in
range
（
amount
+
1
）］
for
_
in
range
（
len
（
coins
）
+
1
）］
dp
［
0
］［
0
］
=
0
for
i
in
range
（
1
，
len
（
coins
）
+
1
）：
for
j
in
range
（
amount
+
1
）：
dp
［
i
］［
j
］
=
dp
［
i
-
1
］［
j
］
if
coins
［
i
-
1
］
<=
j
：
dp
［
i
］［
j
］
=
min
（
dp
［
i
］［
j
］，
dp
［
i
］［
j
-
coins
［
i
-
1
］］
+
1
）
# print（dp）
return
dp
［
-
1
］［
-
1
］
if
dp
［
-
1
］［
-
1
］
！=
float
（
‘inf’
）
else
-
1
class
Solution
：
def
coinChange
（
self
，
coins
：
List
［
int
］，
amount
：
int
）
->
int
：
‘’‘
完全揹包問題，揹包的容量為amount，物品的重量為coins的面額
硬幣的個數無限。 1維寫法
’‘’
dp
=
［
float
（
‘inf’
）
for
_
in
range
（
amount
+
1
）］
dp
［
0
］
=
0
for
i
in
range
（
len
（
coins
））：
for
j
in
range
（
coins
［
i
］，
amount
+
1
）：
dp
［
j
］
=
min
（
dp
［
j
］，
dp
［
j
-
coins
［
i
］］
+
1
）
# print（dp）
return
dp
［
-
1
］
if
dp
［
-
1
］
！=
float
（
‘inf’
）
else
-
1
518 零錢兌換 II（medium）
https：//
leetcode-cn。com/problem
s/coin-change-2/
class
Solution
：
def
change
（
self
，
amount
：
int
，
coins
：
List
［
int
］）
->
int
：
‘’‘
完全揹包問題
dp［i］［j］表示考慮前i種硬幣，湊成金額為j的組合數
狀態轉移：
dp［i］［j］ = dp［i-1］［j］+dp［i-1］［j-c］+dp［i-1］［j-2*c］+。。。+dp［i-1］［j-k*c］
由於dp［i］［j-c］ = dp［i-1］［j-c］ + dp［i-1］［j-2*c］ + 。。。+dp［i-1］［j-k*c］
因此dp［i］［j］ = dp［i-1］［j］ + dp［i］［j-c］
’‘’
if
not
coins
：
if
amount
：
return
0
else
：
return
1
dp
=
［［
0
for
_
in
range
（
amount
+
1
）］
for
_
in
range
（
len
（
coins
））］
for
i
in
range
（
amount
+
1
）：
if
i
%
coins
［
0
］
==
0
：
dp
［
0
］［
i
］
=
1
for
i
in
range
（
1
，
len
（
coins
））：
for
j
in
range
（
amount
+
1
）：
if
j
<
coins
［
i
］：
dp
［
i
］［
j
］
=
dp
［
i
-
1
］［
j
］
else
：
dp
［
i
］［
j
］
=
dp
［
i
-
1
］［
j
］
+
dp
［
i
］［
j
-
coins
［
i
］］
# print（dp）
return
dp
［
-
1
］［
-
1
］
class
Solution
：
def
change
（
self
，
amount
：
int
，
coins
：
List
［
int
］）
->
int
：
‘’‘
完全揹包問題 1維寫法
’‘’
if
not
coins
：
if
amount
：
return
0
else
：
return
1
dp
=
［
0
for
_
in
range
（
amount
+
1
）］
dp
［
0
］
=
1
for
i
in
range
（
len
（
coins
））：
for
j
in
range
（
coins
［
i
］，
amount
+
1
）：
dp
［
j
］
+=
dp
［
j
-
coins
［
i
］］
# print（dp）
return
dp
［
-
1
］
139 單詞拆分（medium）
https：//
leetcode-cn。com/problem
s/word-break/
class
Solution
：
def
wordBreak
（
self
，
s
：
str
，
wordDict
：
List
［
str
］）
->
bool
：
dp
=
［
False
］
*
（
len
（
s
）
+
1
）
dp
［
0
］
=
True
for
i
in
range
（
1
，
len
（
s
）
+
1
）：
for
word
in
wordDict
：
if
（
i
>=
len
（
word
）
and
s
［
i
-
len
（
word
）：
i
］
==
word
）：
dp
［
i
］
=
dp
［
i
］
or
dp
［
i
-
len
（
word
）］
return
dp
［
-
1
］
377 組合總和 Ⅳ（medium）
https：//
leetcode-cn。com/problem
s/combination-sum-iv/
遞迴方法，超時
class
Solution
：
def
combinationSum4
（
self
，
nums
：
List
［
int
］，
target
：
int
）
->
int
：
‘’‘
DFS，先用遞迴
’‘’
def
helper
（
nums
，
target
）：
if
target
<
0
：
return
if
target
==
0
：
self
。
res
+=
1
for
i
in
range
（
len
（
nums
））：
helper
（
nums
，
target
-
nums
［
i
］）
self
。
res
=
0
if
not
nums
：
return
0
helper
（
nums
，
target
）
return
self
。
res
class
Solution
：
def
combinationSum4
（
self
，
nums
：
List
［
int
］，
target
：
int
）
->
int
：
‘’‘
與完全揹包問題有所不同，這裡實際上是排列問題，不同順序的組合看作是不同的結果
dp［i］表示組成目標為i的組合數的數目
’‘’
if
not
nums
：
if
target
：
return
0
else
：
return
1
dp
=
［
0
］
*
（
target
+
1
）
dp
［
0
］
=
1
for
i
in
range
（
1
，
target
+
1
）：
for
num
in
nums
：
if
i
>=
num
：
dp
［
i
］
+=
dp
［
i
-
num
］
return
dp
［
-
1
］