Extending Binary Strings with DP

All the examples below use Distributing DP to extend the strings. If you’ve only solved problems with Receiving DP so far, this style might be difficult to comprehend. You can solve ABC179D: Leaping Tak and ABC335F: Hop Sugoroku in O(n^2) to get accustomed to this style of DP. I also created a video editorial for the latter.

As a refresher, this is Receiving DP

dp[i][j] = something

This is Distributing DP

dp[i + x][j + y] += something + dp[i][j] + otherthing

Problem Link

Find the number of binary strings of length n.

Define dp[i] to be the number of binary strings of length i. You can extend this string by appending either a 0 or 1. Hence,

// Append a zero.
dp[i + 1] += dp[i]

// Append a one.
dp[i + 1] += dp[i]

You can find the code here

Problem Link

Call a binary string good if it has no consecutive zeroes. Find the number of good binary strings of length n.

If you define dp[i] to be the number of good binary strings of length i, you won’t be able to extend this string without knowing the character at the last position. This hints us that we also need to track the last character as a parameter in our DP.

Define dp[i][char] to be the number of good binary strings ending at char. If char = 1, we can append either a 0 or 1, but if char is 0, we are forced to append a 1.

// Append a 1
dp[i + 1][1] += dp[i][1]
dp[i + 1][1] += dp[i][0]

// Append a 0
dp[i + 1][0] += dp[i][1]

You can find the code here

Problem Link

Call a binary string good if it doesn’t contain k consecutive zeroes as a substring. Find the number of good binary strings of length n.

Just tracking the last character isn’t sufficient anymore. We can only safely extend the string when we know the count of suffix zeroes. Define dp[i][x] to be the number of good strings that has x suffix zeroes. Then, if x == k - 1, we are forced to append a 1, else we can append either a 0 or 1. Notice that if you append a 0, the suffix zero count increses, but if you append a 1, the suffix zero count is reset.

// Append a 1.
dp[i + 1][0] += dp[i][x]

// Append a 0.
if(x + 1 < k) {
    dp[i + 1][x + 1] += dp[i][x]
}

You can find the code here

Problem Link

Call a binary string good if it doesn’t k consecutive zeroes as a substring and it has no substring 000...1...000 such that if there are x zeroes to the left of 1 and y zeroes to the right of 1, then x + y should not be equal to k. Find the number of good binary strings of length n.

Now, tracking the count of suffix zeroes is not sufficient anymore, because you can only extend the string if you also know the count of zeroes to the left of the last occurrence of 1.

Define dp[i][x][y] to be the number of good strings whose suffix has x zeroes, followed by a 1, followed by y zeroes. Then, you can append 1 anytime, but you can append a 0 only if x + y + 1 != k. If you append a 1, the suffix zeroes would be reset, and x would be replaced by y. If you append 0, only y would increase.

// Append a 1.
dp[i + 1][y][0] += dp[i][x][y]

// Append a 0.
if(x + y + 1 < k) {
    dp[i + 1][x][y + 1] += dp[i][x][y]
}

You can find the code here

Problem Link

Remember, earlier we told you that extending a string is not possible without storing additional states such as x and y? Turns out, it is indeed possible, if you do the transitions in bulk.

For the K-Zero Stream (Hard Version) : Define dp[i][x] to the be the number of good binary strings that has a suffix consisting of x zeroes. We are not allowed to track y anymore. So, to ensure that x + y < k, we need to do all transitions at once because we would forget those information if we do it step by step.

If the current string consists of x suffix zeroes, then we can try to extend this string by adding 1 or 10 or 100 or 1000 or 1000... where the new string has a suffix consisting of y zeroes. Then, dp[i][x] would contribute to dp[i + 1 + y][y] for all y such that x + y < k.

// Append 1 followed by y zeroes
for y = 0; x + y < k; y++ {
    dp[i + 1 + y][y] += dp[i]
}

You can find the code here

If you’re looking for some more problems where dropping a parameter seems impossible at first, but is actually possible, try ABC334F: Christmas Present 2. I also created a video editorial for it. Here, you might think that it’s impossible to distribute gifts if you don’t keep a parameter to track how many presents are remaining when you reach the i-th child, but you’ll love the cleverness of the final DP definition.

Easy Version : Problem Link Original Version : Problem Link

If you’ve really understood the tutorial so far, you should close this page and solve this problem in O(n^3) time and O(n^2) space by yourself. You can come back to it for the final optimized solution.

int nxt = i + 1 + y
// Append a 1
dp[nxt][y][0] += dp[i][x][y]

// Append a 0
if(x + y + 1 < k) {
    int nxt = i + x + 1
    dp[nxt][x][y + 1] += dp[i][x][y]
}

// Append 10000... (y zeroes at the end)
for(int y = 0; x + y < k; y++) {
    int nxt = i + (x + 1)*(y + 1)
    if(nxt <= n) {
        dp[nxt][y] += dp[i][x]
    }
}

// Append 10000... (y zeroes at the end)
for(int y = 0; x + y < k; y++) {
    int nxt = i + (x + 1)*(y + 1)
    if(nxt <= n) {
        dp[nxt][y] += dp[i][x]
    } else {
        break
    }
}

How to drop parameter for binary strings no consecutive zeroes?

// Append a 1
dp[i + 1] += dp[i]

// Append a 10
dp[i + 2] += dp[i]

How are strings with no consecutive zeroes and Fibonacci number related?

How to drop parameter for no k zero stream?

for x = 0; x < k; x++ {
    dp[i + 1 + x] += dp[i]
}

How to find strings with atleast 3 Consecutive zeroes?

Thanks to aryanc403 for showing me the trick of dropping parameters from DP and doing transitions in bulk.