ZOJ 1883 Tight Words

轉移方程：

F(i, k) = F(i-1, k-1) + F(i-1, k) + F(i-1, k+1)

F(i, k) 表示第i個位置之前的總方案數，其中最後一位為k。

我很納悶的是，這樣子寫，精度竟然沒有問題。

求出總數，然後計算百分比。

[cpp]
#include <cstdio>  
#include <cstring>  
using namespace std; 
double f[102][13]; 
int n, k; 
 
int main() { 
    while (scanf("%d%d", &k, &n) == 2) { 
        k++; 
        memset(f, 0, sizeof(f)); 
        for (int j=1; j<=k; j++) f[1][j] = 1; 
        for (int i=2; i<=n; i++) for (int j=1; j<=k; j++) 
                f[i][j] = f[i-1][j-1] + f[i-1][j] + f[i-1][j+1]
            ; 
        double s = 0; 
        for (int i=1; i<=k; i++) s+= f[n][i]; 
        s *= 100.0; 
        for (int i=0; i<n; i++) s /= (double)k; 
        printf("%.5lf\n", s); 
    } 
    return 0; 
}