DP — Decision Problem using Tabulation

The three most common types of problems in dynamic programming are - 1. decision problem, 2. combinatorics problem, and 3. optimization problem. So, without further ado let’s check out how to solve a decision problem using the bottom-up approach in dynamic programming.

What is a decision problem?

A decision problem is a problem that can be posed as a yes or no question. For example, to assess whether the given number is a prime number or not? the answer to the question can be only either yes or no.

What is a bottom-up approach of DP?

DP is all about solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution of its subproblems.

In the bottom-up approach, we start in hopes of finding the optimal solution for the base case subproblem. We then use this result to solve the next level of smaller sub-problems that will be indeed needed to solve the larger sub-problems. We keep building the solutions iteratively for all sub-problems to find the optimal solution for the actual problem which was posed.

Another term, which is often associated with the bottom-up approach in DP is tabulation. Tabulation is a method by which we cache the intermediate solutions of the sub-problems in a table-like structure. (Usually, a matrix, although note that in some problems such as the Fibonacci we don’t need to tabulate the intermediate solutions to the subproblems, we can just keep track of the solutions to the previous two stages of the current state)

Note

This is a continuation of my previous blogs on DP, so if you’re new to DP and want to learn more about solving decision problems using DP, you can refer to one of my previous blogs over here:

DP — Decision Problem using Memoization

Okay now we have got all that covered, let’s take an example of a decision problem and try to solve it. Here is the problem statement, given a target word and a word bank(array of words) we must determine whether the target word can be built from the word bank or not?

e.g:-

target = “abcd” word bank = [“a”, “b”, “ab”, “cd”]

The answer to the above example is yes, it is possible to construct the target word from the given word bank. we can form “abcd” using {“a”, “b”, “cd} or {“ab”, “cd”}, but we don’t care how the word is formed we’re focused on whether there exists a feasible solution or not.

Intuition

Before jumping into the algorithm, let’s take some time to think about a possible to this problem. One way to approach this problem is that we can form combinations of all the words given in the word bank, and later check whether the target word exists in the combination pool which we have built. This solution will work definitely but it won’t be an effective solution for real-world problems, as the time complexity is in the order of factorial.

So why don’t we think about this problem in terms of dynamic programming? We can view the posed problem as subproblems such that if a particular prefix is possible to construct then we’re only worried about finding a suffix that will go along with the prefix constructed which indeed helps us to construct the target word.

target word = “abcde”, if it is possible to construct “ab” then we’re focused on finding whether there is a word in word bank which could go along as a suffix to “ab” which will help us construct the target word, some possible suffixes are “cd” and “cde”; one important thing to note that is we can’t consider “de” as a possible suffix unless and unitl we can reach a prefix “abc”, as we have to maintain the original order of character occurrences in the target word

So, what is the prefix which will be available regardless of the words in the word bank?

It is the empty string, which can be constructed without taking any words from the word bank, so now we have our base case. Now let’s try picking words from the word bank and check if it is the prefix of the target word, if so we keep track of this word. Now we in turn search for suffixes for the chosen word so that we can construct the given target word.

Algorithm

1. Initialize a boolean array ‘dp’ of size n + 1, where n is the size of the target word.
2. We assign true to index 0, as we know that an empty string can be formed either way with or without taking a word from the word bank.
3. Now, we start iterating through the ‘dp’ array, which is similar to iterating the target word character by character.
4. If dp[i] == false, we skip the iteration as we can’t reach the prefix of the target word using the words from the word bank.
5. Else, if a word from word bank can be found as a suffix from the ith index of the target word, then we set dp[i + length_of_word] = true.
6. We continue this process until either we get true at the final index or we have exhausted all possible combinations after iterating through the array.

Note

dp[i] = true means that it’s possible to construct a substring consisting of characters from the 0th index to the i-1th index. So, when we’re at the 0th index we’re actually making the statement about the empty string.

Simulation of the algorithm

Simulation of the algorithm

1. Initially, we have TRUE at index 0, as it is possible to construct an empty string.
2. Now, we choose the words from the word bank which occurs as a prefix in the target word.
3. So we choose ‘ab’ and mark 2 indexes from the 0th index as true, as we can know it is possible to construct a string until ab, but not ‘abc’.(Remember, when we’re at a particular index, we’re usually making the logical assessment until the i -1 th index but not about the index itself)
4. Next, we choose ‘abc’ and mark 3 indexes from the 0th index as true, which implies that it is possible to construct until ‘abc’. A similar process is carried out for ‘abcd’.
5. Now we have exhausted the word bank, so now we move to the next index in the array.
6. As we see it is false, at no point we will be able to construct ‘a’ from the words from the word bank, so move on to the next index.
7. Now, this process is carried out until we reach true at the final index or we have exhausted all possible combinations. In this case, we get true at n + 1 th index so, we terminate the process.

Code

Code in java for the can construct problem using tabulation

The time complexity of the above code is O(m²*n), where m is the length of the target word and n is the size of the word bank.

Note

Let’s quickly look at the basic steps involved in constructing a tabulation algorithm:

1. Visualize the problem as a table with proper dimensions suiting the inputs.
2. Initialize the table with the default values.
3. Fit the base case answers into the table.
4. Iterate through the table and fill the current position based on the results of the previous positions in the table.

Quick Recap

1. We saw about ‘What is a decision problem?’ and an example problem to go with it.
2. We saw about the intuition on how to solve this problem using dynamic programming.
3. Then we used tabulation to make the algorithm work efficiently.

What’s Next?

The problem which we have discussed today can be found on leetcode, you could try solving it, using the tabulation approach which we have discussed:

Word Break - LeetCode

If you’re able to solve the problem above, you could try this problem over here, which is basically an extension of the same problem:

Word Break II - LeetCode

So, we have come to the end of this post, and thank you so much 😊 if you have made it this far into this post. I will see you in my next post with a combinatorics problem and how to solve the same using tabulation.

References

1. https://www.youtube.com/watch?v=oBt53YbR9Kk&t=16150s
2. https://www.javatpoint.com/tabulation-vs-memoization