洛谷P1754 球迷购票问题 题解 动态规划

题目链接：https://www.luogu.com.cn/problem/P1754

解题思路：

定义状态 (f[i][j]) 表示前 (i) 个人中 (50) 元纸币比 (100) 元纸币多 (j) 张时的方案数，则 (f[i][j] = f[i-1][j+1] + f[i-1][j-1])。

示例代码：

#include <bits/stdc++.h>
using namespace std;
int n;
long long f[55][55];
int main() {
    cin >> n;
    f[0][0] = 1;
    for (int i = 1; i <= 2*n; i ++) {
        for (int j = i%2; j <= min(2*n-i, i); j ++) {
            f[i][j] = f[i-1][j-1] + f[i-1][j+1];
        }
    }
    cout << f[2*n][0] << endl;
    return 0;
}