動态規劃攻略之：傳遞資訊

題目

小朋友 A 在和 ta 的小夥伴們玩傳資訊遊戲，遊戲規則如下：

1. 有 n 名玩家，所有玩家編号分别為 0 ～ n-1，其中小朋友 A 的編号為 0
2. 每個玩家都有固定的若幹個可傳資訊的其他玩家（也可能沒有）。傳資訊的關系是單向的（比如 A 可以向 B 傳資訊，但 B 不能向 A 傳資訊）。
3. 每輪資訊必須需要傳遞給另一個人，且資訊可重複經過同一個人

給定總玩家數 n，以及按 [玩家編号,對應可傳遞玩家編号] 關系組成的二維數組 relation。傳回資訊從小 A (編号 0 ) 經過 k 輪傳遞到編号為 n-1 的小夥伴處的方案數；若不能到達，傳回 0。

示例1：

輸入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3

輸出：3

解釋：資訊從小 A 編号 0 處開始，經 3 輪傳遞，到達編号 4。共有 3 種方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。      

示例2：

輸入：n = 3, relation = [[0,2],[2,1]], k = 2

輸出：0

解釋：資訊不能從小 A 處經過 2 輪傳遞到編号 2      

限制：

2 <= n <= 10
1 <= k <= 5
1 <= relation.length <= 90, 且 relation[i].length == 2
0 <= relation[i][0],relation[i][1] < n 且 relation[i][0] != relation[i][1]      

解題思路

假設目前我們已經走了 i 步，所在位置為 j，那麼剩餘的 k - i 步，能否到達位置 n - 1，僅取決于「剩餘步數 k - i」和「邊權關系 relation」，而與我是如何到達位置 i 無關。

而對于方案數而言，如果已經走了 i 步，所在位置為 j，到達位置 n - 1 的方案數僅取決于「剩餘步數 i - k」、「邊權關系 relation」和「花費 i 步到達位置 j 的方案數」。

定義 f[i][j] 為目前已經走了 i 步，所在位置為 j 的方案數。

那麼 f[k][n - 1] 為最終答案，f[0][0] = 1 為顯而易見的初始化條件。

不失一般性的考慮，f[i][j] 該如何轉移，f[i][j] 應該為所有能夠到達位置 j 的點 p 的 f[i - 1][p] 的總和：

代碼實作

class Solution {
    public int numWays(int n, int[][] relation, int {
        int[][] dp = new int[k + 1][n];
        dp[0][0] = 1;
        for (int i = 0; i < k; i++) {
            for (int[] edge : relation) {
                int src = edge[0], dst = edge[1];
                dp[i + 1][dst] += dp[i][src];
            }
        }
        return dp[k][n - 1];
    }
}      

最後

1. 關注公衆号---​​HelloWorld傑少​​