a O(n^2) solution for SRM517D1_600pt

I just reduce this problem to another:

Given the relations(larger than or less than) of permutations, find out how many permutation satisfy the relations.

(D-f[i]>f[i+1],I-for f[i]<f[i+1])

if the relation is 'DD',then there is only one permutation satisfies the relation:3 2 1.

if the relation is 'DI',then there is two permutations satisfy the relation:3 1 2,2 1 3.

if i-th relation is D,assign a direct edge from i to i+1.

if i-th relation is I,assign a direct edge from i+1 to i.

(DI - 1->2<-3,DD - 1->2->3)

then the ans is the number of topological sorts of this graph.

A friend told me he solved this problem use a n^2 dp:

dp[i][j] is the number of ways which I have decided the i-th number,and there is still j unused numbers larger than the i-th number.

(note that if there is n relations in total,then there is n+1 numbers.)

take an example:

if the relation is DI

dp[1][1]=2 - 21(only 3 is larger than 1 and 2 is uesed),31.(32 is invaild,because there is no unused number than 2).

it's obvious that any instance of the SRM517_600pt can be reduce to this problem's and can be solved by n^2(and I passed the ST).

it's my code(you can view my whole code in the practice room):

for(int i=0;i<=n;i++) dp[0][i]=1;

for(int i=1;i<=n;i++)

{

if (f[i]==1)

{

int sum=0;

for(int j=n-i;j>=0;j--)

{

dp[i][j]=(0ll+dp[i][j]+dp[i-1][j+1]+sum)%m;

sum=(sum+dp[i-1][j+1])%m;

}

if (f[i]==2)

{

int sum=0;

for(int j=0;j<=n-i;j++)

{

dp[i][j]=(0ll+dp[i][j]+dp[i-1][j]+sum)%m;

sum=(sum+dp[i-1][j])%m;

}

int ans=0;

for(int i=0;i<=n;i++) ans=(ans+dp[n][i])%m;

return ans;

I just wonder,is there any batter explain for this algorithm?