整型数组arr长度为n(3 <= n <= 10^4)，最初每个数字是<=200的正数且满足如下条件： 1. arr[0] <= arr[1]。2.arr[n-1] <= arr[n-2]。3. arr[i] <= max(arr[i-1], arr[i+1])。但是在arr有些数字丢失了，比如k位置的数字之前是正数， 丢失之后k位置的数字为0。 请你根据上述条件， 计算可能有多少种不同的arr可以满足以上条件。比如 [6,0,9] 只有还原成 [6,9,9]满足全部三个条件，所以返回1种。
这道题有难度。看答案用到了动态规划。时间太晚了，所以写得简单。
代码用golang编写。代码如下：
package main
import (
"fmt"
)
func main() {
arr := []int{6, 0, 9}
ret := ways3(arr)
fmt.Println(ret)
}
func ways3(arr []int) int {
N := len(arr)
dp := make([][][]int, N)
for i := 0; i < N; i++ {
dp[i] = make([][]int, 201)
for j := 0; j < 201; j++ {
dp[i][j] = make([]int, 3)
}
}
if arr[0] != 0 {
dp[0][arr[0]][0] = 1
dp[0][arr[0]][1] = 1
} else {
for v := 1; v < 201; v++ {
dp[0][v][0] = 1
dp[0][v][1] = 1
}
}
presum := make([][]int, 201)
for i := 0; i < 201; i++ {
presum[i] = make([]int, 3)
}
for v := 1; v < 201; v++ {
for s := 0; s < 3; s++ {
presum[v][s] = presum[v-1][s] + dp[0][v][s]
}
}
for i := 1; i < N; i++ {
for v := 1; v < 201; v++ {
for s := 0; s < 3; s++ {
if arr[i] == 0 || v == arr[i] {
if s == 0 || s == 1 {
dp[i][v][s] += sum(1, v-1, 0, presum)
}
dp[i][v][s] += dp[i-1][v][1]
dp[i][v][s] += sum(v+1, 200, 2, presum)
}
}
}
for v := 1; v < 201; v++ {
for s := 0; s < 3; s++ {
presum[v][s] = presum[v-1][s] + dp[i][v][s]
}
}
}
if arr[N-1] != 0 {
return dp[N-1][arr[N-1]][2]
} else {
return sum(1, 200, 2, presum)
}
}
func sum(begin int, end int, relation int, presum [][]int) int {
return presum[end][relation] - presum[begin-1][relation]
}执行结果如下：
![2021-04-26：整型数组arr长度为n(3 ＜= n ＜= 10^4)，最初每个数字是＜=200的正数且满足如下条件： 1. arr[0] ＜= arr[1]。2.arr[n-1] ＜= arr](https://ctyun-collect-0531.gdoss.xstore.ctyun.cn/files/2023/05/23/1918ef0e5a794945bf6eeb4040e6a019.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/resize,m_fixed,w_1184 "2021-04-26：整型数组arr长度为n(3 ＜= n ＜= 10^4)，最初每个数字是＜=200的正数且满足如下条件： 1. arr[0] ＜= arr[1]。2.arr[n-1] ＜= arr")
