Beecrowd 1144 問題の解決方法

問題の分析: Beecrowd 1144問題は、与えられた整数Nに対して、1からNまでの整数を使ってできる長さNの数列を作成する問題です。ただし、数列の条件として、隣り合う要素の差の絶対値が1以下でなければなりません。

1. 長さNの数列を表すdp配列を初期化します。
2. dp[i]を、i番目の要素を末尾とする数列の総数とします。
3. dp[i]は、dp[i-1] + dp[i-2]の値となります。ただし、iが1または2の場合は初期値として1を設定します。
4. dp[N]が求める答えとなります。

以下は、動的計画法を用いた解法のPythonコード例です。

def solve_beecrowd_1144(N):
    dp = [0] * (N + 1)
    dp[1] = dp[2] = 1
    for i in range(3, N + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[N]
N = int(input())
result = solve_beecrowd_1144(N)
print(result)

def solve_beecrowd_1144_recursive(N):
    if N <= 2:
        return 1
    else:
        return solve_beecrowd_1144_recursive(N - 1) + solve_beecrowd_1144_recursive(N - 2)
N = int(input())
result = solve_beecrowd_1144_recursive(N)
print(result)