C++でNを1・3・4の和で表現する組み合わせの総数を求める方法（動的計画法）

正の整数 N が入力として与えられます。この記事では、N を「1」「3」「4」のみの合計として表現する方法が何通りあるかを求めるプログラムを紹介します。

例えば N = 4 の場合、「1+1+1+1」「3+1」「1+3」「4」の4通りの表し方があるため、答えは 4 となります。

具体例で理解しよう

例1

入力： N = 5

出力： N を 1、3、4 の和で表現する異なる方法の数：6

解説： 5 は以下のように表現できます。

• 1+1+1+1+1
• 1+3+1
• 3+1+1
• 1+1+3
• 4+1
• 1+4

例2

入力： N = 6

出力： N を 1、3、4 の和で表現する異なる方法の数：9

解説： 6 は以下のように表現できます。

• 1+1+1+1+1+1
• 3+1+1+1
• 1+3+1+1
• 1+1+3+1
• 1+1+1+3
• 3+3
• 4+1+1
• 1+4+1
• 1+1+4

アルゴリズムの考え方

ここでは動的計画法（DP）を使って、N を 1、3、4 の和で表す方法の数を効率よく数えます。配列 arr[i] を用意し、i をそのような和で表現する方法の総数を arr[i] に格納していきます。

まず、ベースケースは次のようになります。

• arr[0] = 1（何も選ばない1通りとみなす）
• arr[1] = 1（「1」の1通り）
• arr[2] = 1（「1+1」の1通り）
• arr[3] = 2（「1+1+1」と「3」の2通り）

それ以降の数 i（4 以上）については、次の漸化式で求められます。

arr[i] = arr[i-1] + arr[i-3] + arr[i-4]

これは「最後に 1 を足した場合」「最後に 3 を足した場合」「最後に 4 を足した場合」の3つの場合に分解できるためです。

手順のまとめ

• 正の整数 N を入力として受け取る。
• 関数 Expres_sum(int N) が N を受け取り、1・3・4 の和で表現する方法の数を返す。
• 結果を保存するための配列 arr[N+1] を用意する。
• ベースケースとして arr[0] = 1、arr[1] = 1、arr[2] = 1、arr[3] = 2 を初期化する。
• i = 4 から i <= N までループ処理を行う。
• 各 i について arr[i] = arr[i-1] + arr[i-3] + arr[i-4] を計算する。
• ループ終了後、arr[N] を結果として返す。

実装例

#include <bits/stdc++.h>
using namespace std;
int Expres_sum(int N) {
    int arr[N + 1];
    arr[0] = 1;
    arr[1] = 1;
    arr[2] = 1;
    arr[3] = 2;
    for (int i = 4; i <= N; i++) {
        arr[i] = arr[i - 1] + arr[i - 3] + arr[i - 4];
    }
    return arr[N];
}
int main() {
    int N = 5;
    cout << "Count of different ways to express N as the sum of 1, 3 and 4 are: " << Expres_sum(N);
    return 0;
}

上記のコードを実行すると、次のような出力が得られます。

出力

Count of different ways to express N as the sum of 1, 3 and 4 are: 6

計算量について

この動的計画法によるアプローチでは、各 i の値を一度ずつ計算するだけなので、時間計算量は O(N)、配列を使用するため空間計算量も O(N) となります。全ての組み合わせを列挙する指数時間の探索に比べ、非常に効率的に答えを求められるのがポイントです。