题目描述：

一段文章仅由0 ~k   k + 1个数字组成，要求相邻两个数字的差值不能大于1.

问文章长度n时，合法的文章占所有文章的百分比。

解题报告：

dp[i][j] = dp[i - 1][j] + dp[i - 1][j + 1] + dp[i - 1][j - 1];

dp[i][j]表示文章第i个数字是j时的情况种数。

那么第i位的数字种数的和sum，再除以所有种数(k+1)^n就是答案。

精度问题：只需要直接用double就可以了，它的有效数字的位数满足条件。

代码如下：

#include<iostream>
#include<cmath>
using namespace std;
int k, n;
double dp[101][10], ans[101][10];
int main()
{
    for(int i = 0; i <= 9; i++)
    {
        for(int j = 0; j <= i; j++)
            dp[1][j] = ans[1][j] = 1;
        for(int j = 2; j <= 100; j++)
        {
            double sum = 0;
            for(int k = 0; k <= i; k++)
            {
                dp[j][k] = dp[j - 1][k];
                if (k - 1 >= 0) dp[j][k] += dp[j - 1][k - 1];
                if (k + 1 <= i) dp[j][k] += dp[j - 1][k + 1];
                sum += dp[j][k];
            }
            ans[j][i] = sum / pow((i + 1) * 1.0, j * 1.0);
        }
    }
    while(scanf("%d%d", &k, &n) != EOF)
        printf("%.5f\n", ans[n][k] * 100);
    return 0;
}