While greedy algorithms are an interesting problem-solving heuristic via local optimization, they may not always give a solution. Dynamic programming is a programming method that motivates exploring the space all possible options (as opposed to greedy) by decomposing the problem into subproblems and then building up solutions to larger subproblems; possibly optimizing the algorithm to a polynomial order of time complexity by choosing a memoized recursive or iterative style of implementation.
Basic Outline of Dynamic Programming
While developing an algorithm for dynamic programming problems, subproblems become very important to be understood. Hence, one needs a collection of subproblems derived from the original subproblem that generally satisfies the following:
- Polynomial number of subproblems
- The original problem can be solved from the subproblems
- Natural ordering/comparison among the subproblems exists
Chicken-and-egg trade-off
Sometimes it can be easier to start the process of designing such an algorithm by finding subproblems that look natural and then figuring out a recurrence that links them together but often, it can be helpful to first define a recurrence by reasoning about the structure of an optimal solution, and then determine which subproblems will be necessary to unwind the recurrence. A chicken-and-egg relationship between subproblems and recurrences is a subtle underlying issue in dynamic programming.
Weighted Interval Scheduling Problem
An interval is defined as a block of time with a start and finish time.
Given a set of intervals with weights/values associated with each, find a set of non-overlapping intervals with maximum possible total weight.
A recursive procedure
In this problem, or in general, any problem, assume that we have the solution of the (k-1)th sub-problem, after which we need to find a way to solve the kth sub-problem with it. But, before proceeding any further, you need to define what is meant by the kth sub-problem.
In the above situation, the kth subproblem is finding a set of the non-overlapping interval from a given set of k intervals. Now, since we are clear about the sub-problem, let us discuss the recursive solution.
The solution is based on a simple binary choice: “To include kth interval or to not include it in optimal solution”
This means we have to decide among two subproblems, one which includes kth interval and the other which does not.
solve(k) = max(w(k) + solve(p(k)), solve(k-1))
where,
solve(i): returns the solution of the ith subproblem
p(i): closest non-overlapping interval on the left of ith interval
w(i): weight of ith interval
Now, we can memoize the recursion by storing the solution of sub-problems in a list.
An iterative procedure
For a list M. We define the iterative solution over the number of intervals as follows:
for k ranging from 0 to k-1:
M[k] = max(w(k) + M[p(k)], M[k-1])
Base case: M[0] = 0
The staircase problem
A person can climb 1 or 2 stairs at a time. Find the number of ways to climb the N stairs.
To reiterate, DP problems can be solved by finding subproblems and then collecting the subproblems’ solution as the solution of the bigger subproblem while maintaining a natural order between the subproblems.
For the staircase problem, it is not hard to build an intuition that the subproblem could be a lesser number of stairs (N-1, N-2 .. and so on), and collecting these subproblems could mean adding them up in some linear fashion with some constants which probably would give the solution to the bigger subproblem.
A Recursive approach
Let’s extend the argument to an extent where it becomes more intuitive for someone who cannot see it.
Suppose the person has to climb N=1000 stairs. When he starts climbing the stairs, he wouldn’t worry whether he’d overclimb the 1000th stair while still standing on the 1st stair itself, given that he can only climb a max of 2 steps. However, he would worry about overclimbing when he reaches closer to the 1000th stair, where closer means the 998th or the 999th stair, which when translated is (1000–1)th or (1000–2)th stair.
The reason behind worrying about overclimbing at the 998th or 999th stair is that he now has to decide about the number of steps to climb, which means the number of steps to climb at a time is ≤2.
The solution is the sum of decisions: “How many number of steps to move as long as I do not overclimb the Nth stair”
The number of ways to climb the Nth stair is the sum of the number of ways to climb the (N-1)th stair (after which the person takes 1 step and reaches the Nth stair) plus the number of ways to climb the (N-2)th step (after which the person two steps and the reaches the Nth stair). Hence,
solve(n) = solve(n-1) + solve(n-2)
Base case: solve(-1)=0, solve(0)=1
Note that the case where the person takes 1 step after (N-2)th step to reach the (N-1)th step is covered in the (N-1)th subproblem itself.
An iterative procedure
The recursive approach is more of an intuition-based approach, but the iterative solution for the staircase problem is more mathematical.
No. of ways to climb 2nd step = 1, i.e., climb 1 step from 1st step
No. of ways to climb 3rd step = 2, i.e., climb two steps from 1st step and 1step from 2nd step
No. of ways to climb 4th step = 3, i.e., climb two steps from 2nd step and 1 step from 3rd step (and the no. of ways to climb the 3rd step is 2)
So, no. of ways to climb 4th step = No. of ways to climb 2nd step + No. of ways to climb 3rd step.
Hence, for a list M, the iterative solution is as follows:
for k ranging from 0 to N:
M[k] = M[k-1]+M[k-2]
Base case: M[0]=0, M[1]=1
Problem Extension: r steps taken at a time
Some solutions on the internet associate the staircase problem to the Fibonacci series. But associating it to linear recurrence relations would help understand the problem better. If the problem is extended to a max of three steps, one would have lesser difficulty recognizing it as a recurrence relation with three terms instead of two. Therefore, if the person can take max R steps (R≥1), the number of ways to climb N stairs would be
Recursive solution
solve(n) = solve(n-1) + solve(n-2) + solve(n-3) +…+ solve(n-r)
Base case: solve(k<0)=0, solve(k=0)=1
Iterative solution
for k ranging from 0 to N+R-2:
M[k] = M[k-1]+M[k-2]+M[k-3]…+M[k-r]
Base case: M[0…r-2]=0, M[r-1]=1
Longest common subsequence (LCS) Problem
Find the longest subsequence common to all sequences in a set of sequences.
This problem is better explained in Wikipedia
