c188 - 拉瑪努金的逆襲

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個正整數 n 的分割數，即將 n 表示成正整數和的方式數。例如，P(4) = 5，因為 4 可以被表示為 4, 3+1, 2+2, 2+1+1, 1+1+1+1。

解題思路

這題可以使用動態規劃來解決。定義 ans[i] 為正整數 i 的分割數。我們可以通過迭代的方式計算 ans[i]。對於每個 i，我們可以將其表示為 j + (i - j) 的形式，其中 j 從 1 到 i。因此，ans[i] 可以通過將 ans[i - j] 加起來得到。

初始條件是 ans[0] = 1，因為空和是 0 的一種分割方式。

程式碼中，ans[i] 儲存了 i 的分割數。外層迴圈遍歷 i 從 1 到 200，內層迴圈遍歷 j 從 i 到 200。在內層迴圈中，ans[j] 加上 ans[j - i]，表示將 i 加到 j - i 的分割中，形成 j 的一個新的分割。

複雜度分析

• 時間複雜度: O(n^2)，其中 n 是輸入的最大值 (200)。因為有兩個嵌套的迴圈，每個迴圈都最多執行 n 次。
• 空間複雜度: O(n)，因為我們使用一個大小為 n+1 的陣列 ans 來儲存分割數。

程式碼

#include <iostream>
using namespace std;
long long int ans[201]={1},n;
int main(){
	for(int i=1;i<201;++i){
		for(int j=i;j<201;++j){
			ans[j]+=ans[j-i];
		}
	}
	while(cin >> n){
		cout << ans[n] << "\n";
	}
}