UVA10721 - Bar Codes(DP)

UVA10721 - Bar Codes(DP)
제목 링크
제목 대의: n,k,m를 주고 BC(n,k,m)bar 코드의 수를 충족시켜야 합니다.n은 이러한 문자열의 길이가 n이고 k는 같은 색을 나타내는 단락에 k단이 있으며 m는 각 단락 내에 최대 m개만 같은 것을 나타낸다.
문제풀이 사고방식: f[n][k][m]: i번째 위치를 나타내는 문자는 현재 k단이 형성되었고 길이는 m이다.f[n][k][m] = f[n + 1][k][m + 1] + f[n + 1][k + 1][1];
코드:

#include <cstdio>
#include <cstring>

const int maxn = 55;

typedef long long ll;
int N, K, M;
ll dp[maxn][maxn][maxn];

void init () {

    memset (dp, -1, sizeof (dp));
}

ll DP (int n, int k, int m) {

    ll& ans = dp[n][k][m];
    if (ans != -1)
        return ans;
    if (n == N) {
        if (k == K)
            return ans = 1;
        return ans = 0;
    }

    ans = 0;
    if (k < K)
        ans += DP(n + 1, k + 1, 1);

    if (m < M)
        ans += DP(n + 1, k, m + 1);
    return ans;
}

int main () {

    while (scanf ("%d%d%d", &N, &K, &M) != EOF) {

        init();
        printf ("%lld
", DP(1, 1, 1));
    }
    return 0;
}