UVA10081 - Tight Words(dp)

UVA10081 - Tight Words(dp)
제목 링크
제목의 대의: 숫자 [0..k]를 주고 이런 서열을 찾아달라고 한다. 길이는 n이고 서로 인접한 두 숫자 사이의 차이는 1을 넘으면 안 된다.이런 숫자 서열이 나타날 확률을 묻는다.
문제풀이 사고방식: 그동안 이 문제를 거꾸로 생각하다가 서로 인접한 숫자의 차이가 1보다 큰 것을 찾아내려고 했는데 결국 이 문제는 정면으로 생각해야 쓰기 쉽다는 것을 알게 되었다.또 하나는 확률을 직접 계산할 생각은 하지 않고 총 몇 가지를 통계해 총수를 나눈다는 것이다.그 결과 9^100이 너무 커서 큰 숫자를 쓸 뻔했어요...기억화 검색, dp[n][num]: 이미 n번째 수까지 배열되었고 n번째 수가num이면 다음 수는num 또는num-1 또는num+1이다. [1.k]에 부합하면.
코드:

#include <cstdio>
#include <cstring>

const int maxn = 105;
const int maxm = 10;

int K, N;
double p[maxn][maxm];

void init () {

    for (int i = 0; i < maxn; i++)
        for (int j = 0; j < maxm; j++)
            p[i][j] = -1.0;
}

double dp(int n, int k) {

    double& ans = p[n][k];            
    if (ans != -1)
        return ans;

    if (n == N)
        return ans = 1.0;

    ans = dp(n + 1, k);
    if (k - 1 >= 0)
        ans += dp(n + 1, k - 1);   
    if (k + 1 <= K)
        ans += dp(n + 1, k + 1);
    ans *= 1.0/(K + 1);
    return ans;
}

int main () {

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

        init();
        double ans = 0;
        for (int i = 0; i <= K; i++)
            ans += dp(1, i);
        printf ("%.5lf
", ans * 100.0/(K + 1));
    }
    return 0;
}