[Decode Ways](https://leetcode.com/problems/decode-ways/)。**2019哔哩哔哩笔试题**。设$A-Z$26个字母对应$[1,26]$个数字，给一串数字，求该串数字能表示成多少种字符串。

思路：设置$dp$数组，其中$dp[i]$表示长度为$i$的数字部分能表示多少种字符串。易得$dp[0]=1$，即空数字表示空字串。然后推状态转移方程，新增一个数字$x$，若$x\in{[1,9]}$，则$dp[i]$至少要等于$dp[i-1]$，因为$x$可以独立表示成一个字母；若$x$跟之前一个数字的范围在$[10,26]$内，说明到达$dp[i]$就有两条路径：$dp[i]=dp[i-1]+dp[i-2]$。注意这里还忽略了一个特殊情况，当$x=0$时，其自身是无法表示字母的，只能跟之前的数字合成$10$或$20$来表示字母。综上，状态转移方程为：
$$
\begin{align}
dp[i]=
\begin{cases}
dp[i-1] & ,s[i-1]\in{[1,9]} \\
dp[i-2] & ,s[i-2:i]=10\ or \ s[i-2:i]=20 \\
dp[i-1]+dp[i-2] & ,s[i-2:i]\in{[11,19]\cup[21,26]} \\
\end{cases}
\end{align}
$$


```python
def numDecodings(self, s: str) -> int:
    n = len(s)
    dp = [0]*(n+1)
    dp[0] = 1

    if s[0] == '0':
        return 0

    dp[1] = 1

    for i in range(2, n+1):
        if int(s[i-2:i]) in (10, 20):
            dp[i] = dp[i-2]
        elif int(s[i-2:i]) in range(11, 27):
            dp[i] = dp[i-1]+dp[i-2]
        elif int(s[i-1]) in range(1, 10):
            dp[i] = dp[i-1]

    return dp[-1]
```




    3



[House Robber II](https://leetcode.com/problems/house-robber-ii/)。同上题，不过现在房子围成了一个圈，此时给出的数组首位相等。

思路：现在首尾相连，那么首尾就成了相邻的情况。直接分成两种情况来分析，有首无尾和无首有尾。，对这两种情况，解法与上题一致。


```python
def rob(nums) -> int:
    if not nums:
        return 0
    if len(nums) < 3:
        return max(nums)

    n = len(nums)
    nums_1, nums_2 = nums[1:], nums[:-1]
    dp_1, dp_2 = [0]*(n-1), [0]*(n-1)
    dp_1[0], dp_2[0] = nums_1[0], nums_2[0]
    dp_1[1], dp_2[1] = max(nums_1[0], nums_1[1]), max(nums_2[0], nums_2[1])

    for i in range(2, n-1):
        dp_1[i] = max(dp_1[i-1], dp_1[i-2]+nums_1[i])
        dp_2[i] = max(dp_2[i-1], dp_2[i-2]+nums_2[i])

    return max(dp_1[-1], dp_2[-1])
```




    3



[House Robber III](https://leetcode.com/problems/house-robber-iii/)。房屋呈二叉树结构，小偷不能连续偷有边相连的房屋，求小偷能偷得的最多财富。

思路：树形DP。每一层有两种选择，偷或不偷，所以需要设置两个dp数组，设$dp_{do}[cur\_node]$表示偷当前节点所能获得的最大财富，$dp_{dont}[cur\_node]$表示不偷当前节点所能获得的最大财富，则态转移方程为：
$$
\begin{align}
dp_{do}[cur\_node]&=cur\_node.val+dp_{dont}[left]+dp_{dont}[right] \\
dp_{dont}[cur\_node]&=max(dp_{do}[left],dp_{dont}[left])+max(dp_{do}[right],dp_{dont}[right]) \\
\end{align}
$$
$dp$数组由底往上更新，可使用递归来实现，最终返回$max(dp_{do}[root],dp_{dont}[root])$。


```python
def rob(root: TreeNode) -> int:
    def dp_rec(node):
        '''
        return (dp_do,dp_dont)
        '''
        if not node:
            return (0, 0)
        if not node.left and not node.right:
            return (node.val, 0)

        do_left, dont_left = dp_rec(node.left)
        do_right, do_right = dp_rec(node.right)

        return (node.val+dont_left+dont_right,
                max(do_left, dont_left)+max(do_right, dont_right))

    return dp_rec(root)
```

[All Possible Full Binary Trees](https://leetcode.com/problems/all-possible-full-binary-trees/)。给$N$个节点，求所有可能的满二叉树结构。

思路：满二叉树的节点数肯定是奇数，如果$N$是偶数直接返回空。设立dp数组，其中$dp[i]$存储$i$个节点下所有可能的满二叉树。新增一个节点时，可把新增的节点作为根节点，然后遍历所有可能的奇数作为左分支的节点数，剩余的节点作为右分支的节点数，分别在$dp$数组中取出所有可能的结构拼接到根节点上。


```python
def allPossibleFBT(N: int):
    if N % 2 == 0:
        return list()

    dp = [list() for _ in range(N+1)]
    dp[1].append(TreeNode(0))

    for node_cnt in range(3, N+1, 2):    # 总结点数
        for left_cnt in range(1, node_cnt-1, 2):    # 左分支节点数
            right_cnt = node_cnt-left_cnt-1    # 右分支节点数

            for left in dp[left_cnt]:
                for right in dp[right_cnt]:
                    root = TreeNode(0)
                    root.left = left
                    root.right = right
                    dp[node_cnt].append(root)

    return dp[-1]
```

[Triangle](https://leetcode.com/problems/triangle/)。给一个三角形数组，求一个自顶向下路径的最小和。
```
   [2],
  [3,4],
 [6,5,7],
[4,1,8,3]
```

思路：很明显的dp问题。若自顶向下计算，边界位置与非边界位置需要分开考虑；自底向上计算，很简单。开一个形状与原数据相同的异构嵌套数组，显然初始状态为$dp[-1]=nums[-1]$，状态转移方程为：

$$
dp[row][col]=min(dp[row+1][col],dp[row+1][col+1])+nums[row][col]
$$


```python
def minimumTotal(triangle) -> int:
    n = len(triangle)
    dp = [[0]*row for row in range(1, n+1)]
    dp[-1] = triangle[-1]

    for row in range(n-2, -1, -1):
        for col in range(row+1):
            dp[row][col] = min(dp[row+1][col],
                               dp[row+1][col+1])+triangle[row][col]

    return dp[0][0]
```




    11



排名问题(2019疯狂游戏笔试题)。有$n$个人，对其进行排名次，允许并列同一名，总共有多少种排序方案。

思路：设立二维dp数组，其中$dp[i][j]$表示将$i$个人排成$j$种名词的排序方案，那么初始dp的第一行与第一列全是$1$，对角线上(没有并列名次)是一个全排列，难点在于状态转移方程。增加一个人且构成$j$种名次的话，那么之前的状态只可能有两种：一是之前的$i-1$个人构成$j$种名次，然后第$i$个人与之前的人并列一个名次，没有增加名次的种类；二是之前$i-1$个人构成$j-1$种名次，第$i$个人独占一位，增加一种名次。得：
$$
\begin{align}
dp[i][j]=j*dp[i-1][j]+j*dp[i-1][j-1]
\end{align}
$$


```python
def ranking(n: int) -> int:
    if n < 0:
        return -1

    dp = [[0] * n for _ in range(n)]
    for row in range(n):
        dp[row][0] = 1
    for col in range(n):
        dp[0][col] = 1
    for idx in range(1, n):
        dp[idx][idx] = dp[idx-1][idx-1]*(idx + 1)

    for row in range(1, n):
        for col in range(1, n):
            if row == col:
                dp[row][col] = dp[row-1][col-1]*(row+1)
            else:
                dp[row][col] = (col + 1) * dp[row - 1][col] + \
                    (col + 1) * dp[row - 1][col - 1]

    res = 0
    for col in range(n):
        res += dp[-1][col]

    return res
```

[Maximal Square](https://www.cnblogs.com/grandyang/p/4550604.html)。**百度2019提前批手撕代码题**。给一个含$0$和$1$的矩阵，求其中$1$构成的最大方阵的面积。

思路：设立二维dp数组，其中$dp[i][j]$表示以$(i,j)$为右下角且包含$(i,j)$位置时的最大全$1$方阵的边长。初始状态，第一行与第一列等于原矩阵的值，然后看状态转移方程。首先只有当$(i,j)$本身为$1$时才有可能构成全$1$方阵，然后看该位置的左边、上边跟左上，包含当前位置时所能构成的最大方阵由其最小值决定，所以有：
$$
\begin{align}
dp[i][j]=
\begin{cases}
0 & ,A[i][j]=0 \\
\min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 & ,A[i][j]=1 \\
\end{cases}
\end{align}
$$


```python
def maximalSquare(matrix) -> int:
    res = 0
    if not matrix or not matrix[0]:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    dp = [[0]*cols for _ in range(rows)]
    res = 0

    for row in range(rows):
        dp[row][0] = int(matrix[row][0])
        res = max(res, dp[row][0])
    for col in range(cols):
        dp[0][col] = int(matrix[0][col])
        res = max(res, dp[0][col])

    for row in range(1, rows):
        for col in range(1, cols):
            if matrix[row][col] == '1':
                dp[row][col] = min(dp[row-1][col],
                                   dp[row][col-1],
                                   dp[row-1][col-1])+1
                res = max(res, dp[row][col])

    return res*res
```

[Arithmetic Slices](https://leetcode.com/problems/arithmetic-slices/)。给一数组，求其中等差数列的个数。要求等差数列的长度至少为$3$。

思路：设立dp数组，其中$dp[i]$表示以$i$结尾且包含$nums[i]$的数字序列能构成多少个等差数列。当新增一个数时，若新数与之前两个数等差，则以$i+1$结尾且包含$nums[i+1]$的等差数列就有$dp[i]+1$个。这里的状态转移方程是个难点，需要举个简单例子在纸上列一下。那么总共的等差数列就是对dp数组求和。


```python
def numberOfArithmeticSlices(A) -> int:
    n = len(A)
    if n < 3:
        return 0
    dp = [0]*n

    for idx in range(2, n):
        if A[idx]-A[idx-1] == A[idx-1]-A[idx-2]:
            dp[idx] = dp[idx-1]+1

    return sum(dp)
```




    3



[Unique Substrings in Wraparound String](https://leetcode.com/problems/unique-substrings-in-wraparound-string/)。给一无限循环的顺序字母序列$abc...xyzabc...$，再给一字串$p$，求字串$p$中有多少子串是$s$的子串。

思路：该题类似于求等差数列，但是数字变成了字符，需要考虑重复的情况，题目中的$s$其实可以忽略。设立大小为$26$的$dp$数组，其中$dp[i]$表示以字符$i$结尾且包含字符$i$的等差字串有多少种。在等差数列那一题中知道，每增加一位，那么种类也是只增加一个的。


```python
def findSubstringInWraproundString(p: str) -> int:
    if not p:
        return 0

    n = len(p)
    dp = [0]*26
    dp[ord(p[0])-97] = 1

    cur_len = 1
    for idx in range(1, n):
        if ord(p[idx])-ord(p[idx-1]) == 1 or ord(p[idx-1])-ord(p[idx]) == 25:
            cur_len += 1
        else:
            cur_len = 1
        dp[ord(p[idx])-97] = max(dp[ord(p[idx])-97], cur_len)

    return sum(dp)
```




    6



[Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/)。给一非空非负数组，判断该数组能否分成和相等的两部分。

思路：01背包的变种。将每个数字看作一个物品，每个物品重量为自身的值，该题需要求能否装满一个负重量为$sum(nums)/2$的背包。


```python
def canPartition(nums) -> bool:
    arr_sum = sum(nums)
    if arr_sum & 1:
        return False

    n = len(nums)
    target_sum = arr_sum//2

    dp = [[False]*(target_sum+1) for _ in range(n+1)]
    for row in range(n+1):
        dp[row][0] = True

    for i in range(1, n+1):
        for j in range(1, target_sum+1):
            dp[i][j] = dp[i-1][j]    # 不拿的情况

            if j >= nums[i-1]:    # 拿取第$i$个数字
                dp[i][j] = dp[i][j] or dp[i-1][j -nums[i-1]]    # 不拿或拿，只要有一种情况满足即满足

    return dp[-1][-1]
```




    True



[Out of Boundary Paths](https://leetcode.com/problems/out-of-boundary-paths/)。给一个$m$行$n$列的矩阵，有一个球在$[i,j]$处，在最多走$N$步的条件下，把这个球移动到矩阵外面有多少条可走的路径。

思路：带时间状态的DP问题，时间维度为$N$。设立三维$dp$数组，其中$dp[t][x][y]$表示走$t$步的情况下从$[x,y]$坐标走出去的解法数。那么状态转移方程为：
$$
dp[t][x][y]=dp[t-1][x-1][y]+dp[t-1][x+1][y]+dp[t-1][x][y-1]+dp[t-1][x][y+1]
$$
分别代表走$t-1$步时上下左右四个格子的解法。


```python
def findPaths(m: int, n: int, N: int, i: int, j: int) -> int:
    dp = [[[0]*n for _ in range(m)] for _ in range(N+1)]

    for z in range(1, N+1):
        for x in range(m):
            for y in range(n):
                up = 1 if x == 0 else dp[z-1][x-1][y]
                down = 1 if x == m-1 else dp[z-1][x+1][y]
                left = 1 if y == 0 else dp[z-1][x][y-1]
                right = 1 if y == n-1 else dp[z-1][x][y+1]
                dp[z][x][y] = up+down+left+right

    return dp[-1][i][j] % 1000000007
```




    6



[Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/)。给两字符串，问最少需要做多少次删除操作才能使得两字符串相等。

思路：该题是求两字符串最长公共子序列的反向题目。设一个二维数组$dp$，其中$dp[i][j]$表示字串$1$的前$i$位与字串$2$的前$j$位的最长公共子序列长度，易得$dp[0][0]=0$。不难得出状态转移方程为：

$$
dp[i][j]=
\begin{cases}
dp[i-1][j-1]+1 & str_{1}[i1]=str_{2}[j1] \\
max(dp[i][j-1],dp[i-1][j]) & str_{1}[i1]{\ne}str_{2}[j1] \\
\end{cases}
$$

原理是这样：若两字符串的某一位置相等，则LCS长度可以直接加一；若不相等，则需要取错位比较下的最大长度。


```python
def minDistance(word1: str, word2: str) -> int:
    len_1, len_2 = len(word1), len(word2)
    dp = [[0]*(len_2+1) for _ in range(len_1+1)]

    for i in range(1, len_1+1):
        for j in range(1, len_2+1):
            if word1[i-1] == word2[j-1]:    # 注意dp索引与字串索引大1
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return len_1+len_2-2*dp[-1][-1]
```




    2



[Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/)。给一字符串，求其最长回文子序列。

思路：找回文的方法就是从中心往两边扩展。因为子序列不要求连续，所以使用dp的方法来解。首先$i$表示当前字串的末尾位置，$i$是从前往后扫描的；令$j$表示当前字串的开始位置，$j$是从$i-1$往前扫描的。设一个二维数组$dp$，其中$dp[i][j]$表示$[j,i]$区间内的最长回文子序列的长度，那么易得有$0\le{j\le{i}}$，所以只使用dp数组的下三角。扩展即可得到状态转移方程：

$$
dp[i][j]=
\begin{cases}
dp[i-1][j+1]+2 & s[i]=s[j] \\
max(dp[i-1][j],dp[i][j+1]) & s[i]\ne{s[j]} \\
\end{cases}
$$

注意最后返回的答案是$dp[-1][0]$。


```python
def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1

    for i in range(n):
        for j in range(i-1, -1, -1):    # j由后往前移
            if s[i] == s[j]:
                dp[i][j] = dp[i-1][j+1]+2
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j+1])

    return dp[-1][0]
```




    2



[Unique Paths II](https://leetcode.com/problems/unique-paths-ii/)。给一$01$矩阵，$0$代表可通行而$1$表示障碍物。从左上角出发到达右下角，问有几条路径。

思路：设立二维$dp$数组，其中$dp[i][j]$表示到达$(i,j)$坐标有几条路径。初始状态就是首行首列，首行首列障碍物后面的坐标都是不可达的，需要特殊处理。而递推式就很简单了：
$$
dp[i][j]=dp[i-1][j]+dp[i][j-1]
$$


```python
def uniquePathsWithObstacles(obstacleGrid) -> int:
    if obstacleGrid[0][0] == 1:
        return 0

    rows, cols = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0]*cols for _ in range(rows)]

    dp[0][0] = 1
    for row in range(1, rows):
        dp[row][0] = dp[row-1][0] if obstacleGrid[row][0] == 0 else 0
    for col in range(1, cols):
        dp[0][col] = dp[0][col-1] if obstacleGrid[0][col] == 0 else 0

    for row in range(1, rows):
        for col in range(1, cols):
            dp[row][col] = dp[row-1][col]+dp[row][col - 1] \
                if obstacleGrid[row][col] == 0 else 0

    return dp[-1][-1]
```




    2



[拼凑硬币](https://www.nowcoder.com/questionTerminal/2479839aa61e44f39aa3268160650e17)。现有$2^{i}$面值的硬币各2个，指定一个值，求出使用这些硬币拼凑的方案数。

思路：设立$dp$数组，其中$dp[i]$表示拼凑$i$有多少种方案。易得初始状态为$dp[0]=dp[1]=1$，状态转移方程是难点。因为每种面值硬币都有两个，且考虑到重复值如$(1,2)$跟$(2,1)$。
$$
\begin{align}
dp[i]=
\begin{cases}
& dp[i/2] , i为奇数\\
& dp[(i-1)/2]+dp[(i-1)/2-1] , i为偶数\\
\end{cases}
\end{align}
$$
因为测试用例有大数，而DP需要计算所有的方案，为省内存使用带```mem```数组的递归。


```python
def coin(n):
    mem = {0: 1, 1: 1}

    def rec(i):
        if i in mem.keys():
            return mem[i]
        elif i & 1 == 1:    # 奇数
            mem[i] = rec(i >> 1)
        else:    # 偶数
            mem[i] = rec(i >> 1)+rec((i >> 1)-1)
        return mem[i]

    return rec(n)
```

[骰子游戏](https://www.nowcoder.com/practice/0e83797c34e54cca91179fe9ad681bc4?tpId=90&&tqId=30849&rp=1&ru=/activity/oj&qru=/ta/2018test/question-ranking)。掷一个骰子$n$次，求累计点数和大于等于$x$的概率。

思路：该题关键是求$n$个骰子点数的分布，设二维$dp$矩阵，其中$dp[i][j]$表示$i$个骰子得到$j$点的期望频率。易得状态转移方程为：
$$
\begin{align}
dp[i][j]&=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3] \\
&+dp[i-1][j-4]+dp[i-1][j-5]+dp[i-1][j-6] \\
\end{align}
$$


```python
def func(n, x):
    dp = [[0] * (6 * n + 1) for _ in range(n + 1)]
    for i in range(1, 6 + 1):
        dp[1][i] = 1

    for i in range(2, n + 1):
        for j in range(i, 6 * i + 1):
            if j > 1:
                dp[i][j] += dp[i - 1][j - 1]
            if j > 2:
                dp[i][j] += dp[i - 1][j - 2]
            if j > 3:
                dp[i][j] += dp[i - 1][j - 3]
            if j > 4:
                dp[i][j] += dp[i - 1][j - 4]
            if j > 5:
                dp[i][j] += dp[i - 1][j - 5]
            if j > 6:
                dp[i][j] += dp[i - 1][j - 6]

    return sum(dp[-1][x:])/sum(dp[-1])
```

[歌单方案](https://www.nowcoder.com/questionTerminal/f3ab6fe72af34b71a2fd1d83304cbbb3?orderByHotValue=1&page=1&onlyReference=false)。现有$X$首$A$分钟的歌和$Y$首$B$分钟的歌，要组成一个总长$K$分钟的歌单有几种方案？输出模$1000000007$的结果。

思路：$01$背包方案数问题。现有$X+Y$件物品，一部分重量为$A$而另一部分重量为$B$，拿满一个负重量为$K$的背包有多少种拿法。


```python
def func(K, A, X, B, Y):
    dp = [[0] * (K + 1) for _ in range(X + Y + 1)]
    w = [0] * (X + Y + 1)
    for i in range(1, X + 1):
        w[i] = A
    for i in range(X + 1, X + Y + 1):
        w[i] = B
    dp[0][0] = 1

    for i in range(1, X + Y + 1):
        for j in range(0, K + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i]:
                dp[i][j] += dp[i - 1][j - w[i]]
                dp[i][j] %= 1000000007

    return dp[-1][-1]
```

2019贝壳笔试题。在你面前依次排着n棵树，而你有两种工具，锯子和斧头，它们砍第$i$棵树的时间分别为$a[i]$和$b[i]$，一开始你拿的是斧头，而砍第$i$棵树前交换工具需要花费$c[i]$的时间，问题来了，依次砍完这些树的时间最短为多少呢？

思路：双状态DP问题，设立两个dp数组$dp_{a}$和$dp_{b}$，其中$dp_{a}[i]$表示用锯子砍第$i$颗树的最小时间点，而$dp_{b}[i]$表示用斧头砍第$i$颗树的最小时间点。因为最开始拿的是斧子，所以初始状态为$dp_{a}[0]=a[0]+c[0]$，$dp_{b}[0]=b[0]$，状态转移方程为：
$$
\begin{align}
dp_{a}[i]&=\min(dp_{a}[i - 1], dp_{b}[i - 1] + c[i]) + a[i] \\
dp_{b}[i]&=\min(dp_{b}[i - 1], dp_{a}[i - 1] + c[i]) + b[i]
\end{align}
$$


```python
import sys

n = int(sys.stdin.readline().strip())
a, b, c = [0] * n, [0] * n, [0] * n

for i in range(n):
    a[i], b[i], c[i] = list(map(int, sys.stdin.readline().strip().split()))


def func(a, b, c):
    dp_a, dp_b = [0] * n, [0] * n

    dp_a[0], dp_b[0] = a[0]+c[0], b[0]

    for i in range(1, n):
        dp_a[i] = min(dp_a[i - 1], dp_b[i - 1] + c[i]) + a[i]
        dp_b[i] = min(dp_b[i - 1], dp_a[i - 1] + c[i]) + b[i]

    return min(dp_a[-1], dp_b[-1])


print(func(a, b, c))
```

[Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)。给一非负整数数组，每个位置上的数字代表该位置的陆地高度，求该地势在雨天的最大蓄水量。

思路：木桶原理，一个坑的最大蓄水量取决于其左右挡板中最低那一块的高度。维护两个数组$left$和$right$，其中$left[i]$记录$i$位置左边的最高挡板高度，$right[i]$记录$i$位置右边的最高挡板高度。当前位置的最大蓄水量为：

$$
min(left[i],right[i])-height[i]
$$


```python
def trap(height) -> int:
    n = len(height)
    res = 0
    if n < 3:
        return res

    left, right = [0]*n, [0]*n

    left[0] = height[0]
    for i in range(1, n):
        left[i] = max(left[i-1], height[i])

    right[-1] = height[-1]
    for i in range(n-2, 0, -1):
        right[i] = max(right[i+1], height[i])

    for i in range(1, n-1):
        res += min(left[i], right[i])-height[i]

    return res
```




    6



[Increasing Triplet Subsequence](https://leetcode.com/problems/increasing-triplet-subsequence/)。判断数组中是否存在一个递增的三元组(不要求连续)。

思路：换句话说，去除首尾元素，要在中间元素中找这样一个位置，其左边有小于它的值，其右边有大于它的值。设立两个$dp$数组，```left_min```保存左边的最小值，```right_max```保存右边的最大值。


```python
def increasingTriplet(nums) -> bool:
    n = len(nums)
    left_min, right_max = nums[:], nums[:]

    for i in range(1, n):
        left_min[i] = min(left_min[i-1], nums[i])
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], nums[i])

    for i in range(1, n-1):
        if left_min[i] < nums[i] < right_max[i]:
            return True

    return False
```




    False



[Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/)。给$n$个不同的数字，每个数字形成一个节点，求这些节点能构成多少种不同的BST。

思路：设立$dp$数组，其中$dp[i]$表示$i$个节点所能表示的二叉树的数量。那么对于一个具有$k$个节点，左子树有$i$个节点的二叉树，就有$dp[i]*dp[k-i-1]$种。


```python
def numTrees(n: int) -> int:
    dp = [0]*(n+1)
    dp[0] = 1
    dp[1] = 1

    for k in range(2, n+1):
        for i in range(k):
            dp[k] += dp[i]*dp[k-i-1]
    return dp[-1]
```




    5



[Valid Permutations for DI Sequence](https://leetcode.com/problems/valid-permutations-for-di-sequence/)。给一长度为$n$且只含'D'和'I'的字串，其中'D'表示递减而'I'表示递增。求有多少个长度为$n+1$的自然数排列满足字串限定的大小关系。

思路：**2019爱奇艺笔试题**。设立二维$dp$数组，其中$dp[i][j]$表示长度为$i$且以数字$j$结尾的答案数，易得$j<i$。状态转移方程的推导是难点。假设最后一位要求升序$I$，那么长度为$i$且以数字$j$结尾，前一位必须小于$j$，即：

$$
dp[i][j]=dp[i-1][0]+...+dp[i-1][j-1]
$$

假设最后一位要求降序$D$，同理，前一状态的最后一位都必须大于等于$j$(难点，建议看[此视频](https://www.youtube.com/watch?v=_uqusS_6rvw)了解)，即：

$$
dp[i][j]=dp[i-1][j]+...+dp[i-1][i-1]
$$


```python
def numPermsDISequence(S: str) -> int:
    n = len(S) + 1
    mod = 1e9 + 7
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[1][0] = 1
    for i in range(2, n + 1):
        for j in range(i):
            if S[i - 2] == 'I':
                dp[i][j] = int(sum(dp[i - 1][:j]) % mod)
            else:
                dp[i][j] = int(sum(dp[i - 1][j:]) % mod)

    return int(sum(dp[-1]) % mod)
```

bed1ee7aa55a249f33ebbfe98f0bb900e7035ac8
ipynb
Jupyter Notebook
Algorithm/OnlineExam/Python/DynamicProgramming.ipynb
Daya-Jin/DataStructureAndAlgorithm
212e53e255f103fcf0471bdf9422fd306f3745b5
MIT
2019-03-07T03:19:54.000Z
2019-08-22T08:12:41.000Z
Algorithm/OnlineExam/Python/DynamicProgramming.ipynb
Daya-Jin/DataStructureAndAlgorithm
212e53e255f103fcf0471bdf9422fd306f3745b5
MIT
Algorithm/OnlineExam/Python/DynamicProgramming.ipynb
Daya-Jin/DataStructureAndAlgorithm
212e53e255f103fcf0471bdf9422fd306f3745b5
MIT
Qwen/Qwen-72B
1. YES
2. YES