p23_5
Puting n-1 and then putting nth\nLet\'s change the definition of dp matrix to make the calculation simple: let\'s say dp[i][j] represents the number of permutat
Puting n-1 and then putting nth\nLet\'s change the definition of dp matrix to make the calculation simple: let\'s say dp[i][j] represents the number of permutation of number 0, 1, ... , i which ends with j. Also, it represents the answer of s.substring(0, i) which ends with j.\nWe will have two conditions:\n\ns.charAt(i - 1) == \'I\': In this case, dp[i][j] = sum(dp[i - 1][0], dp[i - 1][1], ... , dp[i - 1][j - 1]).\ns.charAt(i - 1) == \'D\': In this case, dp[i][j] = sum(dp[i - 1][j], dp[i - 1][j + 1], ... , dp[i - 1][i - 1]).\nImagine each time when appending the j to the previous permutations, you have to add 1 to each number in the previous permutation which is greater than or equals to j. In this way, we keep the orders and counts of previous permutations and cumulate.\n\neg. We already have permutation (1, 0, 3, 2). We are trying to append 2. Now the (1, 0, 3, 2) changes to (1, 0, 4, 3) then appended with a 2. We have (1, 0, 4, 3, 2). Although the values change but the order and count don\'t change.\nWhy in case of D, <=l is used explanation\nMethod:\nstep 1.\nfor the original permutation 1032, we add 1 to the digits that are larger than or equal to 2.\n\n1032->1043\n  ^^\nstep 2.\nthen directly append 2 to 1043, i.e., 1043 -> 10432\n\nRemark on step 1:\n(1) By performing add operation, 2 in the original permutation now becomes 3, and thus there is no duplicate element for the new arrival 2.\n(2) More importantly, such operation on the digits will not break the original DI-rule. e.g., 1043 still keeps its old DI-rule, i.e., "DID". The proof is straight-forward, you can validate yourself.
[]