b229 - TOI2009 第一題：路徑問題

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算從原點 (0, 0) 出發，經過 N 個相異邊的路徑數量，其中路徑可以向右、向左或向上移動。

解題思路

這道題目可以利用動態規劃來解決。定義 dp[i] 為長度為 i 的路徑數量。觀察可以發現，長度為 i 的路徑，其最後一步可以是從長度為 i-1 的路徑向右或向上移動，也可以是從長度為 i-2 的路徑向左移動。因此，dp[i] 可以由 dp[i-1] 和 dp[i-2] 推導出來。具體遞迴關係為 dp[i] = 2 * dp[i-1] + dp[i-2]。題目給定的 N 的範圍較小，可以直接使用陣列儲存 dp 值，並從 dp[2] 開始計算，直到 dp[n]。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(n)

程式碼

#include <stdio.h>
unsigned long long dp[51]={1,3};
int n;
int main(){
	for(int i=2;i<=50;++i)
		dp[i]=(dp[i-1]<<1)+dp[i-2];
	while(scanf("%d",&n)>0)
		printf("%llu\n",dp[n]);
}