louisfghbvc的部落格

題目大意:  問有幾種排隊方式不用找錢

思路:  遞迴dp。記憶化搜索。反正坑就是C++過不瞭。數字太大，不夠存。python才能過。這題在DP題庫(C_DP11)有，而且C++能過。

簡單來說，紀錄3個狀態，記得記憶化搜索 估算一下大概O(N^3). 轉移O(1) 

2 Case: 能100塊，要看之前有沒有50塊且100塊人數還有人。至於說順序問題其實很簡單，把這些全部50元100元看成同一個就能處理了

50塊的人如果有就繼續遞迴。使用lru_cache。無腦dp。python太強大了，當然你也可以紀錄一個陣列。

程式碼蠻簡單的。如下。

代碼:  

from functools import lru_cache 
for _ in range(int(input())):
    a, b = map(int, input().split(','))
    @lru_cache(None)
    def dfs(x, y, tot):
        if x == 0 and y == 0: return 1
        res = 0
        if x: res += dfs(x-1, y, tot+1)
        if y and tot: res += dfs(x, y-1, tot-1)
        return res
    print(dfs(a, b, 0))