leetcode.5391. 生成数组

$Description$
图片说明

$Code$
设 $dp[i][j][k]$ 表示数组的第 $i$ 位最大值是 $j$ 且比较次数是 $k$ 的方法数
那么其中一个就是第 $i-1$ 位，最大值在 $[1,j-1]$ 且比较次数是 $k-1$ ，
即 $dp[i-1][1,j-1][k-1]$ 转移过来的。
还有一种情况是第 $i-1$ 位的最大值也是 $j$ ,那么第 $i$ 位可以选择的数字肯定是 $[1,j]$ ,
所以转移的方程是 $dp[i-1][j][k]\cdot j$
所以 $dp[i][j][k]=\sum_{t=1}^{j-1}dp[i][t][k-1]+dp[i-1][j][k]\cdot j$

const mod int64 = 1000000007
func numOfArrays(n int, m int, w int) int {
    if w==0{
        return 0;
    }
    var dp [55][105][55]int64
    for i:=1;i<=m;i++{
        dp[1][i][1]=1;
    }
    for i:=2;i<=n;i++{
        for j:=1;j<=m;j++{
            for k:=1;k<=w;k++{
                for l:=1;l<j;l++{
                    dp[i][j][k]+=dp[i-1][l][k-1]
                    dp[i][j][k]%=mod
                }
                dp[i][j][k]+=dp[i-1][j][k]*(int64(j))%mod
                dp[i][j][k]%=mod
            }
        }
    }
    var ans int64 =0
    for i:=1;i<=m;i++{
        ans+=dp[n][i][w]
        ans%=mod
    }
    return (int)(ans)
}

还有一种是用上python里的lru_cache ,这玩意居然有记忆化的功能

from functools import lru_cache
mod = 1000000007
class Solution:
    def numOfArrays(self, n: int, m: int, w: int) -> int:
        @lru_cache(None)
        def dp(i,j,k)->int:  #位置i放j时比较次数还有k的方法数
            if k<0:return 0
            if i+k>n or j+k>m:return 0
            if i==n and k==0:return 1
            ans=0
            for num in range (1,m+1):
                if num>j:
                    ans+=dp(i+1,num,k-1)
                else:
                    ans+=dp(i+1,j,k)
                ans%=mod
            return ans
        return dp(0,-1,w)