一直搞不懂要怎么把题目的叙述化成递回关系式子
像是Rosen的第七版离散 p.510的第4和p.511的第8题
4. A country uses as currency coins with values of 1 peso,
2 pesos, 5 pesos, and 10 pesos and bills with values of
5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos.
Find a recurrence for the number of ways to pay a bill
of n pesos if the order in which the coins and bills are paid matters.
助教给的答案是
An = An-1 + An-2 + 2*An-5 + 2*An-10 + An-20 + An-50 + An-100
8. Find a recurrence relation for the number of bit strings
of length n that contain three consecutive 0s.
Ans:
分成4个case讨论，ending with 1, 10, 100, and 000
An = An-1 + An-2 + An-3 + 2^(n-3)
不懂为什么要分成4个case讨论
也不太懂为什么1结尾时，会有An-1种组合，
最后000结尾时，又为什么是2^(n-3) @@
有没有大大能用比较浅显的方式说明呢？
或是有哪位老师的讲义比较推荐的
谢谢~

Q8来说 是因为包含连续0的字串长度n-1,n-2和n-3分别是互斥的关系才能这样扣掉吗?那为什么不用0开头 或是11 111之类的分case讨论呢

Q8:"不太懂为什么1结尾时，会有A_(n-1)种组合"长度n-1的合法字串共A_(n-1)种，在上述字串结尾接上1，就变成长度n且合法的字串。长度n且1结尾的合法字串,去掉结尾1,就变成长度n-1的合法字串。由上可知，长度n且1结尾的合法字串，与长度n-1的合法字串，为1-to-1的对映关系。

了解 所以是先假设结尾1是合法字串那n-1就一定是合法字串 然后递回下去感谢J大！