louisfghbvc的部落格

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

題目大意:  給出x值，算出有幾種不同班運方法

思路:  動態規劃，每種狀態可以由1, 2, 3而來。用記憶化搜索加快。預處理建表。

代碼:  

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

int dp[35];
int dfs(int x){
    if(x == 0) return 1;
    if(dp[x]) return dp[x];
    int res = 0;
    for(int i = 1; i <= min(x, 3); ++i){
        res += dfs(x-i);
    }
    return dp[x] = res;
}

int main()
{
    int k, x;
    cin >> k;
    memset(dp, 0, sizeof dp);
    dfs(30);
    while(k--){
        cin >> x;
        cout << dp[x] << endl;
    }
    return 0;
}