设计思想之动态规划

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

什么是动态规划

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

应用动态规划的示例

硬币找零问题

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)