問題描述

長度為 n 的序列，每位取值 0~k。相鄰兩位差值 ≤ 1。求滿足條件的序列佔所有 (k+1)^n 序列的比例（概率）。

從計數 DP 到概率 DP

計數 DP：dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]，最終除以 (k+1)^n。但 n ≤ 100, k ≤ 9 時，(k+1)^n 極大，雙精度溢出。

概率 DP：直接傳遞概率，dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]) / (k+1)。初始 dp[1][j] = 1/(k+1)。答案為 sum(dp[n][j])。

代碼實現

#include <iostream>
#include <cstdio>
using namespace std;

double dp[105][15]; // dp[長度][末尾值]

int main() {
    int k, n;
    while (scanf("%d%d", &k, &n) == 2) {
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= k; ++j)
                dp[i][j] = 0;
        
        for (int j = 0; j <= k; ++j) dp[1][j] = 1.0 / (k + 1);
        
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                dp[i][j] = dp[i-1][j] / (k + 1);
                if (j > 0) dp[i][j] += dp[i-1][j-1] / (k + 1);
                if (j < k) dp[i][j] += dp[i-1][j+1] / (k + 1);
            }
        }
        
        double ans = 0;
        for (int j = 0; j <= k; ++j) ans += dp[n][j];
        printf("%.5f\n", ans * 100); // 題目要求百分比
    }
    return 0;
}

關鍵優化點

1. 滾動數組：dp[i] 只依賴 dp[i-1]，可壓縮為兩行 dp[2][15]。
2. 邊界處理：j=0 無 j-1，j=k 無 j+1，分支判斷避免越界。
3. 輸出格式：題目要求百分比保留 5 位小數，printf("%.5f\n", ans * 100)。

複雜度

• 時間：O(n·k)，n≤100, k≤9 極快。
• 空間：O(k) 滾動後。

舉一反三

類似「相鄰差值受限」的序列計數/概率問題，均可用概率 DP 避免大數溢出。關鍵在於將歸一化因子提前融入遞推，而非最後除法。