c731 - 走路時要算數學

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在二維平面上，從原點出發，恰好走 n 步，且每一步只能向右、向上或向左走，不經過已走過的點的走法總數，並將結果模 12345。

解題思路

這道題可以使用動態規劃來解決。定義 dp[i][j] 表示走了 i 步後，狀態為 j 的走法數量，其中 j 的取值範圍為 0 到 3，分別代表：

• 0: 只能向右或向上走
• 1: 可以向右、向上或向左走
• 2: 只能向左或向上走
• 3: 所有方向都可以走

狀態轉移方程如下：

• dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % 12345
• dp[i][1] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 12345
• dp[i][2] = (dp[i-1][1] + dp[i-1][2]) % 12345
• dp[i][3] = (dp[i][0] + dp[i][1] + dp[i][2]) % 12345

初始條件為 dp[1][0] = dp[1][1] = dp[1][2] = 1，dp[1][3] = 3。

最終答案為 dp[n][3]。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int dp[10001][4],n;
int main(){
	dp[1][0]=dp[1][1]=dp[1][2]=1;
	dp[1][3]=3;
	for(int i=2;i<10001;++i){
		dp[i][0]=(dp[i-1][0]+dp[i-1][1])%12345;
		dp[i][1]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%12345;
		dp[i][2]=(dp[i-1][1]+dp[i-1][2])%12345;	
		dp[i][3]=(dp[i][0]+dp[i][1]+dp[i][2])%12345;
	}
	while(cin >> n)
		cout << dp[n][3] << "\n";
}