動態規劃
- 爬梯子
思路：n阶楼梯最后一步要么是从n-1阶走一步，要么是从n-2阶走两步，所以n阶走的方式等于n-1加上n-2方式总和 – 斐波拉契数
def climb_stairs(n):
a = b = 1
for _ in range(n):
a, b = b, a + b
return a
- Num decodings
‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26
For example, Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12) The number of ways decoding “12” is 2
思路：和爬梯子解法一致，只是多了一个条件，两步时，必须小于27
def num_decodings(s):
if not s or s[0] == "0":
return 0
wo_last, wo_last_two = 1, 1
for i in range(1, len(s)):
x = wo_last if s[i] != "0" else 0
y = wo_last_two if int(s[i - 1:i + 1]) < 27 and s[i - 1] != "0" else 0
wo_last_two, wo_last = wo_last, x + y
return wo_last
s = "121212"
assert num_decodings(s) == 13
- House robber
题目：抢劫沿街的房屋。每间房都藏有一定的现金，阻止你抢劫他们的唯一的制约因素就是相邻的房屋有保安系统连接，如果两间相邻的房屋在同一晚上被闯入，它会自动联系警方。
思路：判断当前房子抢劫与否，依赖于上一个房子和上上一个房子是否抢劫，上上个房屋最优解加上当前房屋现金和上个房屋最优解比较大小选择
def robber(houses):
last, now = 0, 0
for h in houses:
tmp = now
now = max(now, last + h)
last = tmp
return now
houses = [1, 2, 16, 3, 1, 15, 3, 12, 1]
assert robber(houses) == 44
- 背包问题
题目：窃贼偷窃一家有n件物品的商店，第i件物品价值为vi元，重量为wi，假设vi和wi都为整数。他希望带走的东西越值钱越好，但他的背包中之多只能装下W磅的东西，W为一整数。应该带走哪几样东西？
思路：当选择是否要放入第i个物品时，主要考虑放入i物品的价值和不放入i物品的价值
class Item(object):
def __init__(self, weight, value):
self.v = value
self.w = weight
def max_value(items, knapsack):
dp = [[0] * len(items) for _ in range(knapsack + 1)]
for c in range(1, knapsack + 1):
if items[0].w <= c:
dp[c][0] = items[0].v
for index in range(1, len(items)):
if items[index].w <= c:
dp[c][index] = max(
items[index].v + dp[c - items[index].w][index - 1], dp[c][index - 1])
else:
dp[c][index] = dp[c][index - 1]
return dp[-1][-1]
items = [Item(5, 12), Item(4, 3), Item(7, 10), Item(2, 3), Item(6, 6)]
assert max_value(items, 15) == 25
- 单词分割
思路：对每一个字符建索引，然后搜索子字符串是否在字典中
def word_break(s, word_dict):
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(0, i):
if dp[j] and s[j:i] in word_dict:
dp[i] = True
break
return dp[-1]
s = "nevertaomore"
dic = ["never", "more", "tao", "nev"]
assert word_break(s, dic) == True
