Hi everyone. I'm having trouble thinking about a dp problem. The problem is:t There are n students with height from 1->n and one number k(n<=2000, k<=n) You have to line up ALL students so that one person in front of the first person and can see exactly k faces. Example: 2 5 1 6 3 4 => that person can see the face of 1st, 2nd and 4th student. Your work is count how many ways to line up ALL n students. (module 1e9+7)
Test Inp: 3 2 => Output 3 (2 1 3, 1 3 2, 2 3 1)
Thanks for your help.
//Ps Sorry, I am not good at English :((
Auto comment: topic has been updated by TwinHter (previous revision, new revision, compare).
Hint : use dp[i][j] is number of ways to sort i student and we can see j student from head. dp[i][j]=dp[i-1][j]*(i-1)+dp[i-1][j-1].After use combination to calculate the answer. ps: i need you help me to be a master.
I can understand dp[i-1][j-1] but i cant understand dp[i-1][j]*(i-1). Can you explain that?
What I understand we are going in descending order, initially we've i-1 students, so there are i total places for ith student:
Case 1: If we place him behind anyone(i-1 choices) we will not see him and so number of students visible remains the same. We get (i-1)*(dp[i-1][j]) term.
Case 2: If we place him infront the number of students visible increase by 1 so we get dp[i-1][j-1] term.
oh I understanded. I thought the i_th student is the tallest.
Thanks a lot.