LeetCode 1866. 恰有 K 根木棍可以看到的排列数目**

感觉这道题只能背；

之前自己考虑的事把最高的插入k-1～n的位置，转化为子问题；

但是看到这样的思路会超时；

可以根据递推方程优化，但是自己当场肯定优化不出来；

简单的思路是，只看最后一个位置；

如果最后一个位置能看到，说明最高的在最后一个位置，只需要找dp[n-1][k-1]；

如果最后一个位置看不到，则说明有一个矮子在最后一个位置上，但是前半部分依然有序；

可以在最后一位放n-1个矮子，因此有（n-1）*dp[n-1][k]；

这里要注意一下，为什么不考虑倒数第二位，是因为在dp[n-1][…]中，也会考虑到，不用重新考虑；

using ll=long long;
class Solution {
public:
    int rearrangeSticks(int N, int K) {
        vector>dp(N+1,vector(K+1,0));
        ll mod=1000000007;
        dp[0][0]=1;
        for(int n=1;n<=N;n++){
            for(int k=1;k<=K;k++){
                dp[n][k]=dp[n-1][k-1]%mod+((n-1)*dp[n-1][k])%mod;
                dp[n][k]%=mod;
            }
        }
        return dp[N][K];
    }
};