This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
/*
小马需要将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;
