Baekjoon - Sum of 1, 2, 3

Baekjoon - 9095 : Sum of 1, 2, 3

Description

Each time you can either climb 1, 2, or 3 steps. In how many distinct ways can you add up to the input - n?

Example

4

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
1 + 3
3 + 1

Total 7 Ways to Reach 4 using numbers 1, 2 & 3

Input

3 // number of inputs
4
7
10

Output

7
44
274

Approach

This is a very similar problem to the algorithm problem explained previously - Leetcode - Climbing Stairs
By using dynamic programming, numbers of distinct ways to the number can be calculated.

Solution (C++)

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

int N; 
int K;
deque<int> dq; 
deque<int> temp;

int main()
{
    cin >> N;

    dq.push_back(1);
    dq.push_back(1);
    dq.push_back(2);

    for (int i = 1; i <= N; i++)
    {
        cin >> K;

        for (int j = 3; j <= K; j++)
        {
            dq[j] = dqj-1] + dq[j-2] + dq[j-3];
        }
        temp.push_back(dq[K]);
    }


    for (int i = 0; i < N; i++)
    {
        cout << temp[i] << endl;
    }
}