Java, time O(N^2), space O(N), 3ms=>2ms, dp[n+1]
\npublic int numPermsDISequence(String s) {\n\tint n = s.length();\n\tint[][] dp = new int [n+2][2];\n\tint mod = 1000000007;\n\tdp[1][0] = 1;\n\tfor(int i = 1;
```\npublic int numPermsDISequence(String s) {\n\tint n = s.length();\n\tint[][] dp = new int [n+2][2];\n\tint mod = 1000000007;\n\tdp[1][0] = 1;\n\tfor(int i = 1; i<=n; i++){\n\t\tif(s.charAt(i-1)==\'I\') {\n\t\t\tfor(int j = 0; j<=i; j++) dp[j+1][i&1]=(dp[j][(i+1)&1] + dp[j][i&1])%mod;  \n\t\t} else {\n\t\t\tfor(int j = 0; j<=i; j++) dp[j+1][i&1]=((dp[i][(i+1)&1] + mod - dp[j][(i+1)&1])%mod + dp[j][i&1])%mod;\n\t\t} \n\t}\n\treturn dp[n+1][n&1];\n}\n```\nfrom dp[][] to dp[]\n```\npublic int numPermsDISequence(String s) {\n\tint n = s.length();\n\tint mod = 1000000007;\n\tint[] dp = new int[n+1];\n\tdp[0] = 1;\n\tint c, sum,prev;\n\tfor(int i = 1; i<=n; i++){\n\t\tif(s.charAt(i-1)==\'I\') {\n\t\t\tsum = 0;\n\t\t\tfor(int j = 0; j<=i; j++){\n\t\t\t\tprev = sum;\n\t\t\t\tsum = (sum+dp[j])%mod;\n\t\t\t\tdp[j] = prev;    \n\t\t\t} \n\t\t} else {\n\t\t\tc = dp[i-1]+mod;\n\t\t\tsum = c%mod;\n\t\t\tfor(int j = 0; j<=i; j++) {\n\t\t\t\tprev = sum;\n\t\t\t\tsum = (sum+(c-dp[j])%mod)%mod;\n\t\t\t\tdp[j] = prev;    \n\t\t\t }\n\t\t} \n\t}\n\treturn dp[n]%mod;\n}\n```
['Dynamic Programming', 'Java']