[題解]TIOJ 1354 池塘裡的青蛙

tioj-1354 池塘裡的青蛙

題序
這是一個排列組合的數學題目，透過動態規劃紀錄小問題的答案

定義

定義$dp[i][0]$為跳i次不回到A的方法數，$dp[i][1]$為跳i次回到A的方法數

轉移方式

• $dp[i][1]$ = $dp[i-1][0]$
  應該不難理解，回到A的方法數為上一次不回到A的方法數 * 1
• $dp[i][0] = 3\times dp[i-1][1]+2\times dp[i-1][0]$
  不回到A可以分為2種情況，上一次回到A之後，可以往B,C,D，共三種情況。上一次不回到A的情況中，每一個都有兩個可以去的地方。

邊界條件

$dp[0][1] = 0, dp[0][0] = 1$

程式碼

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,k;

signed main(){
    cin>>t;
    while(t--){
        cin>>k;
        int dp[k+1][2];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 0;dp[0][1] = 1;
        for(int i=1;i<=k;i++){
            dp[i][1] = dp[i-1][0];
            dp[i][0] = 3*dp[i-1][1]+2*dp[i-1][0];
        }
        cout<<dp[k][1]<<endl;
    }
}

複雜度

這一題很討厭的，沒有給定測資的範圍，不然應該是可以直接建表然後用O(1)的複雜度求答案