2021-04-26:整型数组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种。

福大大 答案2021-04-26:

这道题有难度。看答案用到了动态规划。时间太晚了,所以写得简单。

代码用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] }

执行结果如下:

数组的命名规则是什么(整型数组arr长度为n)(1)

***

[左神java代码](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class47/Code02_RestoreWays.java)

,