202005 - 放苹果

题解bywangjiajian

不断递归下一个盘子的情况

如果递归到了放不下的情况，return

如果递归到了一个刚好放得下的情况，ans++

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

int m, n, a[30], ans;

void dfs(int x) {
    if (m < a[x-1])
        return;
    if(x == n) {
        ans++;
        return;
    }
    for(int i=a[x-1]; i<=m; i++) {
        a[x] = i;
        m -= i;
        dfs(x+1);
        m += i;
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        memset(a, 0, sizeof(a));
        ans = 0;
        scanf("%d%d", &m, &n);
        dfs(1);
        printf("%d\n", ans);
    }
    return 0;
}