一直搞不懂要怎麼把題目的敘述化成遞迴關係式子
像是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大！