数据结构学习day7：DP实战
1 0-1背包问题
1.1 问题阐述
有N个物品，和一个容量为V的背包。第i件物品的重量是w[i]，价值是p[i]。求解背包装入哪些物品，获得的价值最大。
问题分析：1）目标：背包价值最大；约束条件：所装入背包的物品重量之和不超过V。
2）设集合表示n个物品，该问题的某一个最优解集合为
;
3）最优子结构：对于最优集合A，其子结构也应该为集合A的最优子集合；
4）递归定义最优解的值：对每个物品有两个选择，放入背包，或者不放入；设表示做出第i次选择后，所选物品放入一个容量为v的背包获得的最大价值。对于第i件物品，有两种选择，放或者不放：
a) 如果放入第i件物品，则表示，前
次选择后所选物品放入容量为
的背包所获得最大价值为
，加上当前所选的第i个物品的价值
即为
。
b) 如果不放入第i件物品，则有，表示当不选第i件物品时，
就转化为前
次选择后所选物品占容量为v时的最大价值
.
则：
上述参考：链接1
1.2 求解最优集合：python demo
class DPzero2one(object):
def __init__(self):
self.V = int(input("请输入背包容量：")) # 30
self.Wlist = input("请输入所有物品的重量：") # 5,9,4,7,10,8,6
self.Plist = input("请输入所有物品的价值：") # 10,16,9,13,18,14,12
self.Wlist = self.Wlist.split(',')
self.Wlist = [int(each) for each in self.Wlist]
self.Plist = self.Plist.split(',')
self.Plist= [int(each) for each in self.Plist]
def best(self):
n = len(self.Wlist)
m = self.V
r = [[0 for i in range(n)] for i in range(m + 1)]
for i in range(min(self.Wlist), m + 1):
for j in range(1, n):
r[i][j] = r[i][j - 1]
if (i >= self.Wlist[j]):
r[i][j] = max(r[i][j - 1], r[i - self.Wlist[j]][j - 1] + self.Plist[j])
print("最优值："+str(r[i][n - 1]))
if __name__=='__main__':
DPzero2one().best()测试输出：
缺点：未能输出最优子集，有待研究。
参考：链接2
2. leetcode # 132. Palindrome Partitioning II
问题：
solution demo:
class Solution:
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
if n <= 1:return 0
dp = [[False] * n for _ in range(n)]
mm = [i for i in range(n+1)]
for end in range(n):
for st in range(end + 1):
if s[st] == s[end] and (end - st <= 2 or dp[st+1][end-1]):
dp[st][end] = True
mm[end+1] = min(mm[end+1],mm[st]+1)
return mm[n]-1参考：链接3
result :
缺点：时间过长。
参考：
链接1：https://blog.****.net/hearthougan/article/details/53869671
链接2：https://blog.****.net/qq_30006749/article/details/86704857