DP related to combination

1866. Number of Ways to Rearrange Sticks With K Sticks Visible

We can use DP to solve this problem, the basic idea is:

The first number is 1: If the first is 1, then we have one element qualify, the rest is k-1. If we subtract the rest element by 1 for each, it will reduce the problem in to 1 to n -1. Which is DP(n-1, k-1)

The first number is not 1:

Then 1 will be less than all the element, we have n-1 way to put 1.

for example, 2 _3_

2 1 3

2 3 1

Code is here.

typedef long long LL;
int dp[1010][1010];
const long long MOD = 1e9 + 7;
class Solution {
public:
    long long f(int n, int k) {
        if(n < k || n<0 || k <0) return 0;
        if (n==0 && k ==0) return 1;
        if ( n == k) return 1;
        if (dp[n][k] != -1) return dp[n][k];
        long long ret;
        ret = f(n-1, k-1)+ f(n-1, k)*(LL)(n-1);
        ret %= MOD;
        return dp[n][k] = ret; 
    }
    int rearrangeSticks(int n, int k) {
        if (n == k) return 1;
        memset(dp, -1, sizeof dp);
        return int(f(n, k)%MOD);
    }
};

A similar problem is this one

Number of Monotonically Increasing Lists

Thanks for reading.