作者mistel (Mistel)
看板Grad-ProbAsk
标题[理工] 演算法
时间Tue Sep 10 19:55:22 2019
https://i.imgur.com/R3LFDQu.jpg
请问这题是完全背包问题吗？
看了蛮久的还是不太懂(a)小题M个子问题跟(b)小题每次有d个选项是怎麽来的
https://i.imgur.com/StqRuub.jpg
请问递回程式的好处并不包含易於debug吗？为什麽？
感谢考题版
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.136.219.48 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1568116524.A.D15.html
1F：推 mathtsai: 题目有误i1,i2,...,id必须为非负整数才有解09/10 20:03
2F：→ mathtsai: 定义dp[k]为金额为k时，所需最少硬币数量09/10 20:06
3F：→ mathtsai: dp[M] = min(dp[M], dp[M-i1]+1, ... , dp[M-id]+1)09/10 20:07
4F：→ mathtsai: dp[1]~dp[M]都必须求 所以有M个子问题09/10 20:08
5F：→ mathtsai: 每个子问题 每次有d个钱币可以选择09/10 20:09
哦哦对耶，上楼梯的问题Q_Q
6F：→ mathtsai: easier than WHAT？ 题目写得不清不楚在干嘛？09/10 20:11
7F：→ mathtsai: 等等我看懂了 应该是两个要比较吧？09/10 20:13
8F：→ mathtsai: 但是这两个程式 应该都很好debug啊= =09/10 20:14
9F：→ mathtsai: 他可能想考 Fib1的递回会被呼叫到好几次的问题吧09/10 20:15
了解
不好意思想再请教两个问题
1.coin change problem可以用greedy方式解吗？
我有查过是说要硬币是钞票的因数才可以？
2.
https://i.imgur.com/r8svDZ1.jpg
这一题的画线部分应该是打错了？
※ 编辑: mistel (114.136.219.48 台湾), 09/11/2019 00:09:05
※ 编辑: mistel (114.136.219.48 台湾), 09/11/2019 00:17:47
10F：→ DLHZ: dp应该还是比较保险一点09/11 08:11
11F：→ DLHZ: 画线应该是j才对 09/11 08:23
12F：推 ekids1234: 35题的b有点看不懂，每次 d 种 : 即使币值最高 10元， 09/11 11:36
13F：→ ekids1234: 在算 M = 9 的时候也要考虑进去吗？ 09/11 11:36
我想电脑还是会考虑进去？！
14F：→ ekids1234: 递回 debug 部分，"一般"是认为递回 coding 直观但是 09/11 11:37
15F：→ ekids1234: debug 难(当初学的时候也是) 09/11 11:37
了解
16F：→ mathtsai: 这题不能用greedy 因为他没用greedy property 09/11 15:26
17F：→ mathtsai: *没有greedy property 09/11 15:28
知道greedy choice 一定在最佳解里，但还是不确定要怎麽判断一个问题有没有greedy cho
ice property...
18F：→ mathtsai: 然後第45题可以用segment tree做到O(n lg n) (笑) 09/11 15:40
QAQ 我真的太菜了
※ 编辑: mistel (223.137.50.75 台湾), 09/11/2019 18:22:44