Dynamic Programming

刷了不少题，做DP问题还是苦手，我觉得难点一是如何分析题目可以用DP去解，二是构建最优函数。这里汇总一些经典DP问题

本文主要汇总一些一维的DP问题。

首先总结解决DP问题的5个步骤：

1. Visualize Examples 可视化用例
2. Find an appropriate subproblem 找一个合适的子问题 
3. Find relationships among subproblem 找出子问题之间的关系 
4. Generalize the relationship 概括关系（寻找最优函数） 
5. Implement by solving subproblems in order 通过按顺序解决子问题来实现

例题：

1. 寻找最大递增数列长度（LIS）

给出一个数列，求包含最大的递增子数列的长度。

例子：

 思路：

• 对于数组A，首先给出一个长度为len(A)的数组
• 初始化数组的每个值为1
• 遍历每个数组 i=(1...len(A))
  • 　　对于数组(1...i)，取k=(1...i)，如果A[k]比A[i]小，那么符合形成这样一个链的条件，让L[i] +1, 这样下次遍历的时候，如果任然满足，会再+1，形成一个链
• 取L[i]的最大值

最优函数：

LIS[n] = 1 + max{LIS[k] | k<n, A[k]<A[n]}

代码：

1 def lis(A):
2     L = [1] * len(A)
3     for i in range(1, len(L)):
4         sub = [L[k] for k in range(i) if A[k] < A[i]]
5         L[i] = 1 + max(sub, default=0)
6     return max(L, default=0)
7 
8 print(lis([3,1,2,9,4,8]))

 

2. 堆箱子

问题：给出一些箱子的长宽高（l, w, h），假设箱子上要放其它箱子，必须满足上面的箱子长宽都小于下箱子，求可以堆叠的最高高度，例图：

思路：

首先将箱子按照长度进行排序，构建箱子数量*0的1维数组，遍历每个箱子，如果箱子之前的箱子能够堆叠，那么这里的h取堆叠的值与当前dp值的最大值。

代码：

 1 import operator
 2 
 3 def maxHeight(boxes):
 4     boxes.sort(key=operator.itemgetter(0))
 5     dp = [0] * len(boxes)
 6     for i in range(0, len(boxes)):
 7         dp[i] = boxes[i][-1]
 8         for j in range(0, i):
 9             if boxes[j][0] < boxes[i][0] and boxes[j][1] < boxes[i][1]:
10                 dp[i] = max(dp[i], dp[j] + boxes[i][-1])
11     return dp[-1]
12 
13 boxes = [(4,5,3), (1,5,4), (2,3,2), (2,4,1), (3,6,2), (1,2,2)]
14 print(maxHeight(boxes))

 

3. 单词拼接

 source: https://leetcode-cn.com/problems/word-break/

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
  注意你可以重复使用字典中的单词。
示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

 

思路：

• 初始化 dp=[False,⋯,False]，长度为 n+1。n 为字符串长度。dp[i] 表示 s 的前 i 位是否可以用 wordDict 中的单词表示。
• 初始化 dp[0]=True，空字符可以被表示。
• 遍历字符串的所有子串，遍历开始索引 i，遍历区间 [0,n)：
  • 遍历结束索引 j，遍历区间 [i+1,n+1)：
  • 若 dp[i]=True 且 s[i,⋯,j) 在 wordlist 中：dp[j]=True。解释：dp[i]=True 说明 s 的前 i 位可以用 wordDict表示，则 s[i,⋯,j) 出现在 wordDict 中，说明 s 的前 j 位可以表示。
• 返回 dp[n]

 

代码：

 1 class Solution:
 2     def wordBreak(self, s: str, wordDict: List[str]) -> bool:       
 3         n=len(s)
 4         dp=[False]*(n+1)
 5         dp[0]=True
 6         for i in range(n):
 7             for j in range(i+1,n+1):
 8                 if(dp[i] and (s[i:j] in wordDict)):
 9                     dp[j]=True
10         return dp[-1]