April 26, 2021: the length of the integer array arr is n (3 ＜ = n ＜ = 10^4), and each number is

2021-04-26： integer array arr The length is n(3 <= n <= 10^4), Initially, each number was <=200 Is positive and satisfies the following conditions ： 1. arr0 <= arr1.2.arrn-1 <= arrn-2.3. arri <= max(arri-1, arri+1). But in arr Some numbers are missing , such as k The number of positions is preceded by a positive number , After losing k The number of positions is 0. Please... According to the above conditions , Calculate how many different arr Can meet the above conditions . such as 6,0,9 Only restore to 6,9,9 All three conditions are met , So back 1 Kind of .

Fuda answer 2021-04-26：

This problem is difficult . The answer is dynamic programming . It's too late , So it's simple .

The code to use golang To write . The code is as follows ：

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]
}

The results are as follows ：

picture

***

Zuo Shen java Code