Dynamic Programming - Gael Yimen Yimga

Dynamic programming is a common subject that can appear in any type of technical interviews. It is defined as a mathematical optimization method and a computer programming method that consists of the selection of the best element, regarding some criterion, from some sets of available alternatives. [1][2].

How to identify a DP problem

Coding interview is another discipline itself and to be successful, you need to know the rules. To identify a dynamic programming problem, there are some clues you need to know.

First, sometime when a question is asking about the number of ways to do something, it could probably be a dynamic programming problem. Let see a second clue that can solidify your thought.
Second, if there is a need to make decision that depends on previously made decisions then we are convince that we are in front of a dynamic programming problem and we need to treat it as such.

How to solve DP problem

A dynamic programming problem has most likely 3 components. The 3 components that we are going to discuss are extremely valuable as most dynamic programming problem can be solved this way.

The first component we need to identify to solve a DP problem is a function or an array that represents the answer to a problem from a given state.
The second component is to identify a way to transition between states. This can be considered as a recurrence relation as we describe in our previous article about recursion. Generally, in DP problem, figuring out the recurrence relation seems to be the hardest part to solve the problem.
The third component is establishing the base cases as in the recursion.

Let discuss all those concepts in a typical DP problem.

Example of problem that we can solve with DP – Leetcode 276 : Paint fence.

Let consider a problem that is titled: Paint Fence. The problem is the number 276 in Leetcode.com. The description of the problem goes:
You are painting a fence of n posts with k different colors. You must paint the posts following these rules:

Every post must be painted exactly one color.
There cannot be three or more consecutive posts with the same color.

Given the two integers n and k, return the number of ways you can paint the fence.

Resolution of previous problem

Is this problem a DP problem?

First the problem is asking about the number of ways to do something, here it is the number of ways to paint fences. Then we need to decide what color we should paint a given post, which may change depending on previous decisions. For instance, if we paint the first two in the same color, then we are not allowed to paint the third post the same color. The answer is YES, we are facing a DP problem.

Solving the problem

First, we need a function or an array that represents the answer to the problem for a given state. For this problem, let say we have a function totalWays, where totalWays(i) returns the number of ways to paint i posts. Because we only have one argument, this is a 1-dimensional DP problem.

Second, the transition between states can be for example totalWays(3) and totalWays(4). We have a paragraph about finding the recurrence relation. We will come back to that later.

Third, let discuss the base cases. If we have one post, there are k ways to paint it, because there are k different colors. If we have two posts, there are k * k ways to paint them because we are allowed to paint two posts in a row with the same color. Therefore totalWays(1) = k, totalWays(2) = k * k

Finding the recursion relation

We know the values for totalWays(1) and totalWays(2), now we need a formula for totalWays(i) when 3 <= i <= n. Let’s think about how many ways there are to point the i-th post. We have two options.

Use a different color than the previous post. If we use a different color, then there are k-1 colors for us to use. This means there are (k-1) * totalWays(i-1) ways to point the i-th post a different color than the (i-1)th post.
Use the same color as the previous post. There is only one color for us to use, so there are 1 * totalWays(i-1) ways to paint the i-th post the same color as the (i-1)-th post. However, we have the added restriction of not being allowed to point three posts in a row the same color. Therefore, we can paint the i-th post the same color as the (i-1)-th post only if the (i-1)-th post is a different color than the (i-2)-th post.
So, how many ways are there to paint the (i-1)-th post a different color than the (i-2)-th post ? Well, as stated in the first option, there are (k - 1)*totalWays(i - 1) ways to paint the i-th post a different color than the (i-1)-th post, so that means there are 1 * (k - 1) * totalWays(i - 2) ways to paint the (i - 1)-th post a different color than the (i - 2)-th post. Adding these scenarios together gives totalWays(i) = (k-1) * totalWays(i-1) + (k -1) * totalWays(i-2) which can be simplified to totalWays(i) = (k-1) * (totalWays(i-1) + totalWays(i-2)). This is our recurrence relation which can be used to solve the problem from base case.

Code


    class Solution {
        private Map<Integer, Integer> map = new HashMap<>();
        public int numWays(int n, int k) {
            // Base cases
            if (n == 1) return k;
            if (n == 2) return k * k;

            // Memoization: Check if we already precalculated the result
            if (map.containsKey(n)) return map.get(n);

            // Recurrence relation to compute
            int result = (k - 1) * (numWays(n - 1, k) + numWays(n - 2, k));

            // Storing the result
            map.put(n, result);

            // Return the result.
            return result;
        }
    }

References

Glossary

DP: Dynamic Programming

← Previous Post Next Post →