Hard DP
Introduction
Dynamic problems are lots of fun. If you do enough practice, you will find the patterns of how to solve the DP problems. In this article, I’d like to summary some hard DP problems.
903. Valid Permutations for DI Sequence
Thinking aloud
The naive solution will get n!, it is not OK as n is as large as 100. From the mod by 1e9+7, we will have the feeling that this problem can be solved by using DP. It is easy to find out that the first digit can be chosen from 0 to n. However, after that, the state transition got stuck as we can not simple define a state of DP[i][j] where i is the string index and j is the value that we pick up. Because if we define it in this way, we can not satisfy the permutation property, which is there is no repeating numbers.
Suppose repeating numbers are allowed, then we can simple apply the above state definitions and then transitions will be:
dp[i+1][j] =
if ‘I’: sum(dp[i][k] for k in range(n) if k<j )
if (this character == 'I'){
for(int k=0;k<j;++k) dp[i+1][j] += dp[i][k]}else
for(int k=j+1;k<n;++k) dp[i+1][j] += dp[i][k]}
It is pretty easy to say that the complexity of the above algorithm is O(n²)
and the space complexity is O(n²)
What is the critical point to solve this problem?
If the simple dp[i][j] definition is not working, can we change the state definition?
- by including the history information?
for example:
43
23
13
03
They all end at 3 and it is in the second symbol. If we are going to increase the value, then ‘43’ is invalid as there is no number greater than 3 (4 is used). This idea looks like the traveling salesman problem. In the TSP problem, we also need to record the history path, and also only the last station matters for future exploration. The complexity of TSP is O(2^n * n²). Since n is large, it seems that this way is not working. However, we can try it although we may get TLE, it can be a good exercise. I tried, however, I found I can not code this solution up.
I’d like to move to a better-defined state.
From HERE:
dp[i][j] means the number of possible permutations of first i + 1 digits,
where the i + 1th digit is j + 1th smallest in the rest of unused digits.
Ok, may not make sense … Let’s see the following diagram.
The intuition is that, given a string s, the result of the permutation of
0, 1,2
1,2,3
1,2,4
are same.
Which means we can use the index of the sorted unused digits to aggregate the results.
I’d like to improve the illustration and also state definition.
I’d like to define the state of DP[i][j] as:
i is the digit index.
j is the index of current digit from current digit + remaining digit.
The reason we define j in this way is
All the following will have the same results based on the same string S.
0, 1,2
1,2,3
1,2,4
We can use index to do a unified representation.
After figuring out this, the transitions can be shown as below:
From the toy example, we can see:
if we have digit from 0 to n, initially we will have index scope of 0 to n
Then the number of the available indexes is decreased by 1 each time as one digit is used for each step. As you can see from the illustration, with the increase of i, the number of blocks is decreased by 1.
Then the transition is pretty natural. For example, if we want to transit from dp[0][3] to dp[1][j] if we are going to decrease the number. We know that if we move from index 3 to 2,1,0, it can be decreased. And hence:
for dp[0][3] if we decrease it in one step, it will go to dp[1][2], dp[1][1], dp[1][0]. Update the corresponding states:
dp[1][2] += dp[0][3]
dp[1][1] += dp[0][3]
dp[1][0] += dp[0][3]The above is looking forward.
If we stand from dp[1][0] and look backward, we will have:
if we change from dp[0][j] to dp[1][0] by increasing the last digit value, how can we do that?
we can go to dp[1][0] from dp[0][1], dp[0][2], dp[0][3]. This is a postfix sum.
/*
jimmy shen
Time complexity: O(n^2)
Space complexity: O(n)
*/int MOD = 1e9+7;
class Solution {
public:
int numPermsDISequence(string S) {
int N = S.size();
vector<int> dp(N+1, 1);
for (int i=1;i<N+1;++i){
int M = (N+1)-i;
vector<int> new_dp(M, 0);
if (S[i-1]=='D'){
//postfix sum
for (int j=dp.size()-2;j>=0;--j){
dp[j] += dp[j+1];
if (dp[j]>=MOD)dp[j] %= MOD;
}
for (int j=0;j<M;++j){
new_dp[j] = dp[j+1];
}
}
else{
//prefix sum
for (int j=1;j<dp.size();++j){
dp[j] += dp[j-1];
if (dp[j]>=MOD)dp[j] %= MOD;
}
for (int j=0;j<M;++j){
new_dp[j] = dp[j];
}
}
dp = new_dp;
}
int ret = 0;
for (int i=0;i<dp.size();++i){
ret+=dp[i];
if (ret>=MOD)ret %= MOD;}
return ret;
}
};
If you wanna practice the 2D DP, here is a code for reference
/*
jimmy shen
using 2d dp to solve this problem
Do not optimize the code, so it has the time complexity of O(n^3)
Space complexity of O(n^2)
*/int MOD = 1e9+7;
class Solution {
public:
int numPermsDISequence(string S) {
int N = S.length()+1;
int M = N;
vector<vector<int>> dp(N, vector<int>(N));
for (int j=0;j<N;++j)dp[0][j]=1;
//push forward
for(int i=0;i<N-1;++i){
M--;
if(S[i]=='D'){
for (int j=0;j<N;++j){
for (int k=0;k<j;++k){
dp[i+1][k] += dp[i][j];
if(dp[i+1][k]>MOD)dp[i+1][k]%=MOD;
}
}
}
else{
for (int j=0;j<N;++j){
for (int k=j;k<M;++k){
dp[i+1][k] += dp[i][j];
if(dp[i+1][k]>MOD)dp[i+1][k]%=MOD;
}
}
}
}
int ret = 0;
for (int j=0;j<N;j++){
ret += dp[N-1][j];
if (ret>MOD)ret%=MOD;
}
return ret;
}
};
