python/TangDou/LanQiaoBei/LanQiaoBei13ShengSai_ZJ_II/7.cpp

/*
小马需要将N件物品从河的一岸搬运到河的另一岸，每次搬运的物品为1到3件。
请问小马将N件物品全部搬运过去有多少种方案。
例如：N=3，将3件物品全部搬运过去有4种方案：
方案一：第一次搬运1件，第二次搬运1件，第三次搬运1件；
方案二：第一次搬运1件，第二次搬运2件；
方案三：第一次搬运2件，第二次搬运1件；
方案四：一次搬运3件。
*/
#include <bits/stdc++.h>

using namespace std;
const int N = 110;
int a[N];
int res;
int n;

/**
 * @brief
 *
 * @param step 第几次
 * @param r  剩余件数
 */
void dfs(int u, int r) {
    if (r == 0) res++; //剩余为0，就得到一组答案

    //本轮运几件
    for (int i = 1; i <= 3; i++)
        if (r - i >= 0) dfs(u + 1, r - i);
}
int main() {
    cin >> n;
    dfs(0, n);
    printf("%d", res);
    return 0;
}