Summary
In some problems, the index i is not enough to make subproblems alg[i] independent to the previous sequences s[0,i-1]. We need one or several extra states to make subproblem self-contained.
The intuition is: if we brute force the problem, there might be many duplicate visitings. For example, two different dfs enter the same index i at the linear sequence, but the later possibilities after i are the same.
If we could add extra states to remember the result of the first run, then we could immediately return at the second run the states are the same.
Details
920. Number of Music Playlists
We define the extra state as the total number of different songs we have played before index i.
The first choice is not different: we play a new song.
alg[i][j] =
1. (N - j) * alg[i + 1][j + 1]The second choice is tricky: when we play an old song, how to ensure that there are at Least K unique songs after last time it got played? Look at the following graph.
.....xxxx i
____
k
_________
j We know the the most recent k plays must contain k unique songs, or any two among them will violate the rules. And there are j unique songs among arr[0,i-1], which means all the (j-k) could be chosen at index i. So we have,
alg[i][j] =
1. (N - j) * alg[i + 1][j + 1]
2. (j - k) * alg[i + 1][j] if j >= k
// alg[L][N] = 1;LC 1444. Number of Ways of Cutting a Pizza
The problem is regarding a 2D matrix but it is still a linear structure. It is not difficult to figure out that we need an extra state to store how many cuts we already have at alg[i, j].
alg[i][j][k] = sum {
1. alg[ii][j][k+1] if curr_pizza > 0 for ii in [i+1, m-1], curr_pizza = sum[i][j] - sum[ii][j]
2. alg[i][jj][k+1] if curr_pizza > 0 for jj in [j+1, n-1], curr_pizza = sum[i][j] - sum[i][jj]
}
// alg[i][j][K - 1] = sum[i][j] > 0 ? 1 : 0
sum[i][j] = pizza[i][j] == 'A' +sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1]