Ý tưởng

Nhận xét:

• Trường hợp đặt biệt: Với ~N \leq K~, ta có thể suy ra công thức nhanh là ~2^{N - 1}~ (Ta có thể phân tích ~N~ thành các số ~1~ và tìm số cách đặt các vách ngăn giữa chúng).

• Trường hợp còn lại: Ta phải thử tất cả cách ghép từ ~1~ đến ~K~, và tiếp tục tìm số cách ghép số mảnh ghép còn lại.

Gọi ~dp[i]~ là số cách ghép ~i~ mảnh ghép thành bức tranh.

Công thức quy hoạch động:

• Trạng thái ban đầu: ~dp[1] = 1~.
• Trường hợp ~i \leq K~: ~dp[i] = 2^{i - 1}~.
• Trường hợp ~i \gt K~: ~dp[i] = \sum^{K}_{j = 1} dp[i - j]~.

Độ phức tạp: ~O(N^2)~.

Code tham khảo

#include<bits/stdc++.h>

using namespace std;

const int maxN = 53;

int n, k;
long long dp[maxN];

void input()
{
    cin >> n >> k;
}

long long POW(int base, int cnt)
{
    if(cnt == 0) return 1;
    if(cnt == 1) return base;
    long long tmp = POW(base, cnt / 2);
    if(cnt % 2) return tmp * tmp * base;
    return tmp * tmp;
}

void solve()
{
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i  = 1; i <= n; ++i)
    {
        if(i <= k) dp[i] = POW(2, i -1);
        else
        for(int j = 1; j <= k; ++j)
        {
            dp[i] += dp[i - j];
        }
    }
    cout << dp[n];
}

int main()
{
    input();
    solve();
    return 0;
}