主題
題目連結：
題目意譯：
你被給定三個整數 n 、 m 和 k。現在考慮以下在一個正整數陣列中找到最大元素的演算法：
你現應建構出一個陣列 arr，其有以下性質：
arr 有著恰好 n 個整數。
1 ≦ arr[i] ≦ m，其中 0 ≦ i < n。
在 arr 上執行上述演算法之後，search_cost 之值等於 k。
回傳建構出符合條件的陣列 arr 之方法數。由於答案可能會太大，答案應先模 10 ^ 9 + 7 再回傳。
限制：
1 ≦ n ≦ 50
1 ≦ m ≦ 100
0 ≦ k ≦ n
範例測資：
範例 1：
輸入： n = 2, m = 3, k = 1
輸出： 6
解釋： 可能的陣列為 [1, 1] 、 [2, 1] 、 [2, 2] 、 [3, 1] 、 [3, 2] 、 [3, 3]
範例 2：
輸入： n = 5, m = 2, k = 3
輸出： 0
解釋： 此例中沒有陣列會滿足條件。
範例 3：
輸入： n = 9, m = 1, k = 1
輸出： 1
解釋： 唯一可能的陣列為 [1, 1, 1, 1, 1, 1, 1, 1, 1]
解題思維：
可以看到，題目給定的演算法是只要現在看到的數值大過「當前最大值」，「當前最大值」便會更新且 search_cost 加 1。
因此如果現在看到的數字是 arr[i]，其只在乎「當前最大值」為何（稱其值為 j）以及現在的 search_cost 之值（將其以 k 代稱，注意此 k 不是題目的 k）。
將原本的演算法重新敘述會變成：
當 arr[i] > j 時，j = arr[i] 、 k = k + 1；
反之，j 、 k 不變。
可以看到三個變數 (i, j, k)，可能會變成 (i + 1, arr[i], k + 1) 或是 (i + 1, j, k)，兩者都是可能的子問題。所以一如既往地，不知道要做哪些子問題，就全做吧！（如這題）
定義一個三維陣列 D，其中 D[i][j][k] 代表著在看到 arr[i] 這個位置並更新完數值之後，「當前最大值」為 j 且 search_cost 為 k 的方法數。可以看到其遞迴式為：
D[0][j][1] = 1，其中 j 為任意正整數；
D[0][j][k] = 0，其中 k != 1；
（上面兩式為遞迴停止條件）
D[i][j][k] = D[i - 1][j][k] × j + D[i - 1][j'][k - 1]，其中 i > 0 、 j 為任意正整數、k ≦ i 且 1 ≦ j' < j。
最後把 D[n - 1][1][k]（注意這邊的 k 變回題目給定的 k 了） + D[n - 1][2][k] + …… + D[n - 1][m][k] 即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
