# 【題解】ZeroJudge d887: 1.山脈種類(chain)

• 先觀察山脈的步數與高度走勢，假設山脈最高高度 i (1 <= i <= j)，總步數 2j (1 <= j <= N)。
• dp[i][j] 有下圖的狀態轉移關係。直接使用二維陣列編寫程式碼（1）
• 或，觀察下表的關係，改用一位陣列編寫，如程式碼（2）

```#include <iostream>
#include <cstring>
using namespace std;

const int maxn=30;
//dp[i][j]:最大高度為i，總步數為2j的組合數
long long dp[maxn][maxn];

int main() {
int N;
while (cin >> N) {
memset(dp, 0, sizeof(dp));
for (int j=1; j<=N; j++) {
// 最大高度為1的組合數
dp[1][j] = 1;
}
for (int i=2; i<=N; i++) {
// 最大高度i, 2 <= i <= N
for (int j=1; j<i; j++) {
//總步數2j, j<i
dp[i][j] = dp[i-1][j];
}
for (int j=i; j<=N; j++) {
//總步數2j, i <= j <= N
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
cout << dp[N][N] << "\n";
}
return 0;
}
```

```#include <iostream>
using namespace std;

int main() {
int n;
while (cin >> n){
long long a[n+1];
for (int i = 0; i <= n; i++){
a[i] = i;
}
if (n >= 3){
for (int i = 3; i <= n; i++){
for (int j = i; j <= n; j++){
a[j] += a[j-1];
}
}
}
cout << a[n] << "\n";
}
}
```

Python code (credit: Amy Chou)

```while True:
try:
n = int(input())
a = [i for i in range(n+1)]

if n >= 3:
for i in range(3, n+1):
for j in range(i, n+1):
a[j] += a[j-1]

print(a[n])
except:
break
```