设计思想之动态规划

什么是动态规划

贪心法就像是理想化的动态规划,每次总是做出在当前看来是最好的选择,而动态规划则需要根据情况进行综合判断。

应用动态规划的示例

硬币找零问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MinCoinCount:
def __init__(self, total):
self.memory = [0 for _ in range(total+1)] # 备忘录
print(self.dp(total))

def dp(self, money):
self.coin = 0 # 需要的硬币数为0
if self.memory[money] != 0: # 在备忘录中寻找该金额下的最少硬币找零数,若存在,则取出
self.coin = self.memory[money]
elif money <= 0: # 边界问题
if money == 0: # 如果金额为零,则代表刚好算是一种找零方法
self.coin = 0
else:
self.coin = float("inf")
elif money > 0:
self.coin = min(self.dp(money-1), self.dp(money-2), self.dp(money-5))+1 # 递归,找出最少的可以凑齐金额数money的方法
self.memory[money] = self.coin
return self.coin

if __name__ == '__main__':
MinCoinCount(22)
0%