也是常见套路。
# coding = utf-8 def rec_mc(coin_value_list, change, know_results): min_coins = change if change in coin_value_list: know_results[change] = 1 return 1 elif know_results[change] > 0: return know_results[change] else: for i in [c for c in coin_value_list if c <= change]: num_coins = 1 + rec_mc(coin_value_list, change-i, know_results) if num_coins < min_coins: min_coins = num_coins know_results[change] = min_coins return min_coins print("===========递归实现========================") print(rec_mc([1, 5, 10, 25], 63, [0]*64)) def dp_make_change(coin_value_list, change, min_coins, coins_used): for cents in range(change+1): coin_count = cents new_coin = 1 for j in [c for c in coin_value_list if c <= cents]: if min_coins[cents-j] + 1 < coin_count: coin_count = min_coins[cents-j]+1 new_coin = j min_coins[cents] = coin_count coins_used[cents] = new_coin return min_coins[change] def print_coins(coins_used, change): coin = change while coin > 0: this_coin = coins_used[coin] print(this_coin) coin = coin - this_coin a_mnt = 63 c_list = [1, 5, 10, 21, 25] c_used = [0] * (a_mnt+1) c_count = [0] * (a_mnt+1) print("===========动态规划实现========================") print('Making change for ', a_mnt, 'requires') print(dp_make_change(c_list, a_mnt, c_count, c_used), 'coins') print("They are: ") print_coins(c_used, a_mnt) print("The used list is as follows: ") print(c_used)
输出:
D:\cheng\test\Scripts\python.exe tests.py ===========递归实现======================== 6 ===========动态规划实现======================== Making change for 63 requires 3 coins They are: 21 21 21 The used list is as follows: [1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1, 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10, 1, 1, 1, 10, 1, 10, 21] Process finished with exit code 0