※ 引述《NTHUlagka (拉卡)》之銘言：
: https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactl
: 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
: 思路：
: 典型的DP題，定義memo[i][j][h]為當在第i個位置且i-1個 elements中最大值為j，
思路：
這題剛開始看有點亂 但了解之後就還好
三維dp陣列 需要很多計算
我寫得有點醜 用了四個for 不過比較好理解過程
先初始化常數項的dp迴圈: dp[1][j][1]為1
比較方便計算後面
因為題目求的是dp[n][m][k]
所以for終止條件是 i <= n/m/k (宣告的Vec大小也都+1)
前三個for就是跑n/m/k
狀態轉移方程的部分：
首先是 dp[i][j][o] = (dp[i][j][o] + (dp[i-1][j][o] * j));
這個是因為我們從dp[i-1][...]到dp[i][...]
從n變成n+1長度的陣列 多了一個空位
而這個新的數字在維持最大值出現o次的情況增加
從結果來講是j種可能性
因為多的一格代表可以在陣列的任意位置塞非最大值的數字
接著是
for p in 1..j {
dp[i][j][o] = (dp[i][j][o] + dp[i-1][p][o-1]) % MOD;
}
剛剛是不新增新的最大值的情況把陣列變大
這邊就是相反 是在陣列變大 且最大值也+1的情況延長陣列
這時候會有三種可能性：
1. 新元素比新的最大值小：最大值數量不會改變
2. 新的元素跟舊的最大值一樣：最大值數量會=舊的最大值數量+1
3. 新的元素跟新的最大值一樣：最大值數量會=1
最後的%MOD則是題目要求 不然數字可能會過大
結果計算：
let mut result = 0;
for j in 1..=m as usize {
result = (result + dp[n as usize][j][k as usize]) % MOD;
}
我們要算n長度下每一種最大值m的可能性
所以就是個Sigma用的方程式
一樣記得%MOD
Code:
impl Solution {
pub fn num_of_arrays(n: i32, m: i32, k: i32) -> i32 {
const MOD: usize = 1_000_000_007;
let mut dp = vec![vec![vec![0; k as usize + 1]; m as usize + 1]; n as
usize + 1];
for j in 1..=m as usize {
dp[1][j][1] = 1;
}
for i in 2..=n as usize {
for j in 1..=m as usize {
for o in 1..=k as usize {
dp[i][j][o] = (dp[i][j][o] + (dp[i-1][j][o] * j));
for p in 1..j {
dp[i][j][o] = (dp[i][j][o] + dp[i-1][p][o-1]) % MOD;
}
}
}
}
let mut result = 0;
for j in 1..=m as usize {
result = (result + dp[n as usize][j][k as usize]) % MOD;
}
result as i32
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1696783529.A.9A1.html
※ 編輯: yam276 (123.193.249.242 臺灣), 10/09/2023 00:47:12