※ 引述《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
}
}