uva 10081 - Tight Words(dp)

题目大意：给出k和n，表示可以用0~k之间的数值来组成长度为n的数组，然后数组中有一种较为特殊的情况，即任意两个相邻的数值的差不超过1，计算这种特殊的数组占总数的百分比。

解题思路：p[i][j]表示说长度为i，且最后一个数字为j的数字占长度为i的数组的百分比。

#include <stdio.h>  
#include <string.h>  
  
int n, k;  
double p[105][15];  
  
void solve() {  
    memset(p, 0, sizeof(p));  
    for (int i = 0; i <= k; i++)  
        p[1][i] = 1.0 / (k + 1);  
    for (int i = 2; i <= n; i++) {  
        for (int j = 0; j <= k; j++) {  
            p[i][j] = p[i - 1][j];  
            if (j) p[i][j] += p[i - 1][j - 1];  
            if (j != k) p[i][j] += p[i - 1][j + 1];  
            p[i][j] /= (k + 1);  
        }  
    }  
}  
  
int main () {  
    while (scanf("%d%d", &k, &n) == 2) {  
        solve();  
        double ans = 0;  
        for (int i = 0; i <= k; i++)  
            ans += p[n][i];  
        printf("%.5lf\n", ans * 100);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,