Dynamic programming

基本思想

动态规划(Dynamic programming,DP),通过把原问题分解为相对简单的子问题的方式分解复杂问题的方法。

使用的情况

能采用动态规划求解的问题一般具有3个性质:

  • 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构;
  • 无后效性:某状态以后的过程不会影响以前的状态,只与当前状态有关;
  • 有重叠子问题:子问题之间不独立,一个字问题在下一阶段中可能被多次使用。(这一性质是动态规划与其他算法相比所具备的优势)

实例

LeetCode: Wildcard Matching
这道题其实就是Regular Expression Matching的简化版,下面主要说一下动态规划的解法。
输入两个字符串s,p,用一个布尔数组dp,dp[n]值表示字符串s前n个字符是否符合模式p。这就将原问题拆分成很多子问题,要想知道s是否匹配p,只需要知道之前匹配结果及当前位匹配情况就可以ok了。
具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
length = len(s)
if len(p)-p.count('*') > length:
return False
dp = [True]+[False]*length
for i in p:
if i != '*':
for n in reversed(range(length)):
dp[n+1]=dp[n] and (i==s[n] or i == '?')
else:
for n in range(1,length+1):
dp[n]=dp[n-1] or dp[n]
dp[0]=dp[0] and i=='*'
return dp[-1]
#test
>>> isMatch('aa','*')
True
>>> isMatch("ab", "?*")
True
>>> isMatch("aab", "c*a*b")
False

分享