终于讲到动态规划了，刚刚面完依图，就考了动态规划，在面试官的提示下才写出来，要是认真刷过题就好了。
Leetcode 53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
解题思路一：动态规划。比较前 i-1 个数的最大子序和+第i个数的和，与第i个数本身的大小比较。
解题思路二：
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = nums
dp[0] = nums[0]
ans = dp[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i-1] + nums[i], nums[i])
if dp[i] > ans:
ans = dp[i]
return ans
Leetcode 120. 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
解题思路：这个题很容易从上往下想，其实要自下而上来思考。
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
n = len(triangle)
i = n - 2
while i >= 0:
for j in range(i+1):
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
i -= 1
return triangle[0][0]
Leetcode 62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
示例 2:
输入: m = 7, n = 3
输出: 28
解题思路：动态规划方法的经典应用，每一个点上面的路径总数都等于它上面和左边的点的路径总数之和。注意这里的mn是列行而不是行*列。
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
if m == 1 or n == 1:
return 1
dp = [[1 for _ in range(m)] for _ in range(n)]
for i in range(1, n):
for j in range(1, m):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[n-1][m-1]
Leetcode 63. 不同路径II
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解题思路：创建一个dp的数组，全部为0，第一位为1-input[0][0]，递推公式为如果input[i][i] == 1的话，则dp[i][j]为0，否则dp[i][j] = dp[i-1][j]+dp[i][j-1]
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m = len(obstacleGrid)
n = len(obstacleGrid[0])
if m == 0:
return 0
if n == 0:
return 0
dp = [[0 for _ in range(n)] for _ in range(m)]
dp[0][0] = 1 - obstacleGrid[0][0]
for i in range(m):
for j in range(n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
if i > 0:
dp[i][j] += dp[i-1][j]
if j > 0:
dp[i][j] += dp[i][j-1]
return dp[m-1][n-1]
Leetcode 91. 解码方法
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
解题思路：注意这里要把dp的长度扩大一位，相应的dp中对应的答案的序号也会后移一位。
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if s[0] == '0' or s == None:
return 0
dp = [0] * (len(s) + 1)
dp[0] = 1
for i in range(1, len(dp)):
if s[i-1] != '0':
dp[i] = dp[i-1]
if i != 1 and '09' < s[i-2:i] < '27':
dp[i] += dp[i-2]
return dp[-1]
Leetcode 198. 打家劫舍
（跪了跪了，去依图现场面试的就是这道题，写了好久好久，哭唧唧，应该多刷刷题的）
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
解题思路：这里的动态规划需要两个变量，一个是偷前面一家，一个是不偷前面一家。
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
f = nums[0]
g = 0
for i in range(1, n):
last_f = f
last_g = g
f = g + nums[i]
g = max(last_f, last_g)
return max(f, g)
Leetcode 300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
解题思路：用数组dp[i]记录以nums[i]结尾（即nums[i]为最后一个数字）的最长递增子序列的长度，则递推方程为dp[i]=max(dp[j]+1)，其中要求1≤j<i且nums[j]<nums[i]。
时间复杂度分析：对每个i(1≤i≤n)，都需要从1遍历到i，则时间复杂度为O(n2)，空间复杂度的话需要一个额外的dp数组，空间复杂度为O(n2)。
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n <= 1:
return n
dp = [1 for _ in range(n)]
length = 1
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
length = max(length, dp[i])
return length
Leetcode 72. 编辑距离
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2:
输入: word1 = "intention", word2 = "execution"
输出: 5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
解题思路：
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
n = len(word1)
m = len(word2)
if n == 0:
return m
if m == 0:
return n
f = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n+1):
f[i][0] = i
for i in range(1, m+1):
f[0][i] = i
for i in range(1, n+1):
for j in range(1, m+1):
if word1[i-1] == word2[j-1]:
f[i][j] = f[i-1][j-1]
else:
f[i][j] = f[i-1][j-1] + 1
f[i][j] = min(f[i-1][j] + 1, f[i][j])
f[i][j] = min(f[i][j-1] + 1, f[i][j])
return f[n][m]
Leetcode 518. 零钱兑换II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2] 输出: 0
你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数
解题思路：
class Solution(object):
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
n = len(coins)
dp = [0 for _ in range(amount+1)]
dp[0] = 1
for i in range(n):
j = coins[i]
while j <= amount:
dp[j] += dp[j-coins[i]]
j += 1
return dp[amount]
Leetcode 664. 奇怪的打印机
有台奇怪的打印机有以下两个特殊要求：
打印机每次只能打印同一个字符序列。
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。
给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。
示例 1:
输入: "aaabbb"
输出: 2
解释: 首先打印 "aaa" 然后打印 "bbb"。
示例 2:
输入: "aba"
输出: 2
解释: 首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
解题思路：
class Solution(object):
def strangePrinter(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
if n == 0:
return 0
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(1, n):
for i in range(n-length):
j = i + length
dp[i][j] = 1 + dp[i+1][j]
for k in range(i+1, j):
if s[i] == s[k]:
dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j])
if s[i] == s[j]:
dp[i][j] = min(dp[i][j], dp[i+1][j])
return dp[0][n-1]
Leetcode 10. 正则表达式
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。
'.' 匹配任意单个字符
'' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a"
输出: true
解释: 因为 '' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = "."
输出: true
解释: "." 表示可匹配零个或多个（''）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "cab"
输出: true
解释: 因为 '' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "misisp."
输出: false
解题思路：
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
n = len(s)
m = len(p)
s = ' ' + s
p = ' ' + p
f = [[False for _ in range(m + 1)] for _ in range(n + 1)]
f[0][0] = True
for i in range(n + 1):
for j in range(1, m + 1):
if i > 0 and (s[i] == p[j] or p[j] == '.'):
f[i][j] = f[i][j] or f[i-1][j-1]
if p[j] == '*':
f[i][j] = f[i][j] or f[i][j-2]
if i > 0 and (s[i] == p[j-1] or p[j-1] == '.'):
f[i][j] = f[i][j] or f[i-1][j]
return f[n][m]
