作者j12345453 (CJentalL)
看板Grad-ProbAsk
标题成大演算法CoinChange
时间Mon Dec 13 17:02:17 2021
https://i.imgur.com/AFM2trb.jpg
想请问各位大佬
题35
a b问题的解答是怎麽来的呢
----
Sent from
BePTT on my iPhone 11
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.72.52.92 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1639386139.A.C60.html
1F：推 jimmy1112111: 类似01背包问题，背包怎麽做的这个也就类似 12/13 17:53
2F：推 A4P8T6X9: 因为换 M 的问题跟如何换 M-1 本质上是一样的问题，所 12/13 18:27
3F：→ A4P8T6X9: 以第一题是 M。 12/13 18:27
4F：→ A4P8T6X9: 对 M 来说，他可以测试每一个 M - C_i，来产生最佳解。 12/13 18:28
5F：→ A4P8T6X9: 所以第二题是 d。 12/13 18:28
6F：→ A4P8T6X9: 不过我也是看答案反推的，感觉就是不敢考 code 只能这 12/13 18:30
7F：→ A4P8T6X9: 样间接考。 12/13 18:30
8F：推 joywilliamjo: 就coin change dp，有a,b,....d种钱币，是否能凑成1 12/13 19:01
9F：→ joywilliamjo: ,2,3,4.....M元 12/13 19:01
10F：→ joywilliamjo: sub problem:可否凑出1元，2元3元.....m元 12/13 19:02
11F：→ j12345453: 通了谢谢各位！ 12/13 22:57
12F：→ j12345453: 不过第二小题D种选择 12/13 22:57
13F：→ j12345453: 我稍微懂 但有点不够清楚 12/13 22:57
14F：→ j12345453: 请问可以再帮我进一步解释吗 12/13 22:57
16F：→ j12345453: 我粗略画了一个DP表格 12/13 23:04
17F：→ j12345453: 我认为萤光笔直行那边是D种选择 12/13 23:04
18F：→ j12345453: 横列是M个子问题 12/13 23:04
19F：→ j12345453: 这样说得通吗 12/13 23:04
20F：→ j12345453: 感觉还少了点什麽 12/13 23:04
21F：→ cossetannie: 假设d=2 c1=1 c2=2, dp[i]=min(dp[i-1], dp[i-2])+1 12/13 23:36
22F：→ cossetannie: 就看你d是多少就有几个sub-problem 12/13 23:37
23F：→ cossetannie: 基本上就可以想成是每次有d种选择一样的意思 12/13 23:38