louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=2599

題目大意:  2種錢, 50, 100元，給你各個持有錢的人數a, b, 問有幾種排列方法使得店員不用找錢。

更新(itsa 202011 P1 解法):  https://louisfghbvc.pixnet.net/blog/post/329039341-itsa-202011-problem-1.-%E6%8E%92%E9%9A%8A

思路:  動態規劃, 記憶化搜索, 常常用到的技巧。首先找出基底, 基底為a == 0或b==0 答案是1種

再來想一下，如何搜索，可以分成兩類，一種為走50元，或走100元。最後在merge。

那走100元有限制，店員的錢必須超過50元。

所以轉移式為 dp[a][b] += dp[a-1][b]。 dp的意思是人數a, b最多能有多少種方式。

          再來     dp[a][b] += dp[a][b-1]。當店員有錢的時候。

圖示:  Example: 3,1 。黑色為葉節點 = 1

代碼:  

#include <bits/stdc++.h>
using namespace std;

int memo[55][55];
int dfs(int a, int b, int sum){
    if(b == 0 || a == 0) return 1;
    if(memo[a][b]) return memo[a][b];
    int res = 0;
    res += dfs(a-1, b, sum+50);
    if(sum > 0) res += dfs(a, b-1, sum-50);
    return memo[a][b] = res;
}

int main()
{
    int a, b;
    scanf("%d,%d", &a, &b);
    printf("%d\n", dfs(a, b, 0));
    return 0;
}

/*
3,1
3,2
2,2
1,1
4,2
*/