Concept
There are 2 basic approaches to solve Dynamic Programming problems:
- Top-down: using recursive calls to generate all possible choices and calculate results. Memoization or array cache could be used to stored and retrieve data on repeated cases. The base cases are cases at the bottom of the decision tree.
- Bottom-up: mentally calculate the base case at the bottom of the decision tree and come up with the equation to calculate the general cases.
When solving the DP problem, we consider the following:
- State:
- State variables
- Base cases
- Recurrence cases
Solving problems will explain the terms a lot better.
From earlier posts LONGEST COMMON SUBSEQUENCE,and MAXIMUM SCORES FROM PERFORMING MULTIPLE OPERATIONS illustrated how Topdown solution is used to construct the decision tree. In particular, we would have a rather simple recursive call such as:
int recursiveCall(vector<int>&inputData, int stateVariableA, int stateVariableB){
// base case
if (stateVariableA = 0)
return cache[stateVariableA][stateVariableB] = someValue;
// memoization
if (cache[stateVariableA][stateVariableB] != -1)
return cache[stateVariableA][stateVariableB]; // return stored value
// recurrence relation
if (some condition){
nextStateVariableA = stateVariableA * someLogic;
return recursiveCall(inputData, nextStateVariableA, nextStateVariableB);
}
else{
nextStateVariableB = stateVariableB * anotherLogic;
return recursiveCall(inputData, nextStateVariableA, nextStateVariableB);
}
}Dynamic Recurrence Relation occurs when we have a range of values for our state variables. For example, the problem, Min Step to Climb Stairs could be changed with conditioned now that each step could be taken up to K stairs.
Top down solution would use iterative DFS algorithm to generate decision trees. The For loop serves as a stack to process iterative recurrence (each loop goes deeper in each branch, each iteration goes wider branch by branch)
int recursiveCall(std::vector<int>& cost, int numberOfSteps) {
// base case : similar implementation
// memoization: similar implementation
// recurrence relation:
// at each i-th step, the current cost is the cost taking up to steps.
int currentCost= INT_MAX;
// use dynamic recurrence relation
// can be applicable if the condition is to take up to K steps.
// DFS algorithm:
for (int step = 1; step <= K; step++) {
currentCost = std::min(currentCost, recursiveCall(cost, step+1);
}
}
return dp[n];
}Sample Problem Minimum Difficulty of A Job Schedule
You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the jobs j where 0 <= j < i).
You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done on that day.
You are given an integer array jobDifficulty and an integer d. The difficulty of the ith job is jobDifficulty[i].
Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.
Example 1:
Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7Explanation:
First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7
If you do 1 job 1 first day. Difficulty is 6.
Second day, you have to finish the remaining jobs, difficulty is 5.
The total difficulty is 6 + 5 = 11
Thus the minimum difficulty of a job schedule is 7
Top-down, Memoization:
Support we have jobDifficulty = [1 4 3 6 4 5 8], and 3 days following brute-force approach, a decision tree could be draw:
The above diagram shows some but not all paths of a decision tree. For each day, there are a number of possible jobs, starting from the a job index that is dependent on previous day. For example:
- if all jobs={1 4 3 6 4 5 8}, and on day 1, the job done are {1}. then on day 2, the jobs could be {4}. {4 3}, {4 3 6} etc, all of which have
startingIndex = 1. - if all jobs={1 4 3 6 4 5 8}, and on day 1, the job done are {1,4,3,6}. then on day 2, the jobs could be {4}. {4 5}, {4 5 8} etc, all of which have
startingIndex = 4. - If we go down the decision tree, where day+1, we also have
new_startingIndex = old_startingIndex +1
The total job difficulty of any day is the sum difficulty of all the previous days. The result is minimum all off possible paths, the minimum of job Difficulty of the last day. Thus we could come up with the following definitions:
- state: the job Difficulty of each day, expressed as `Difficulty` array
- state variables:
startingIndex: the starting job index of that daycurrentDaythe current day
- recurrence relation the jobs could have their indices from
startingIndexto themaximum number of jobfor each day.
min_diff(startingIndex, currentDay) = min_diff(j, currentDay + 1) + max(jobDifficulty[startingIndex:j]) for all j > startingIndex
==> we have j runs from startingIndex to the maximum number of jobs for each day.
==> max number of jobs for each days = total jobs - remaining days- base case: if
remainingDay ==1: the job Difficulty of the day if the maximum jobDifficulty of all remaining jobs.
class Solution {
public:
vector<vector<int>> cache; //row: startingIndex of job on currentDay, col: currentDay, starting from 0
int difficulty ( vector<int>& jobDifficulty, int startingIndex, int currentDay, int maxDay ){
<<currentDay<<endl;
int remainingDay = maxDay - currentDay;
int maxNumberOfJobInTheDay = jobDifficulty.size() - remainingDay;
// memoization:
if (cache[startingIndex][currentDay] != -1)
return cache[startingIndex][currentDay];
// base case: if there is 1 day remaining, finish all jobs
// difficulty is the max difficulty of the remaining jobs
if ( remainingDay == 1 ){
int result = *std::max_element( begin(jobDifficulty) + startingIndex, end(jobDifficulty) );
return result;
}
// recursive cases:
int dailyMaxJobDiff = 0;
int nextDayJobDiff = 0;
int result = INT_MAX;
// DFS process: the for loop runs like a stack (FIFO)
// it goes deeper in each branch, branch i =0, i = 1, i = ..., i = maxNumberOfJobInTheDay
for (int i = startingIndex; i <= maxNumberOfJobInTheDay; i++) {
dailyMaxJobDiff = max (jobDifficulty[i], dailyMaxJobDiff) ;
nextDayJobDiff = difficulty(jobDifficulty, i+1, currentDay+1, maxDay); // recursive case: goes deeper, thus i+1 is used as input
result = min(dailyMaxJobDiff + nextDayJobDiff, result );
}
return cache[startingIndex][currentDay]=result;
}
int minDifficulty(vector<int>& jobDifficulty, int d) {
cache.resize(jobDifficulty.size(), vector<int>(d,-1));
if (jobDifficulty.size() < d)
return -1; // cannot assign the work during the number of day
return difficulty(jobDifficulty, 0, 0, d);
}
};Analysis:
Program flow
The above algorithm makes use of recursive call which allows the program to traverse along the decision tree. We implement a for loop and a recursive function Difficulty which takes 2 state variables index of the job and the currentDay.
for (int i = startingIndex; i <= maxNumberOfJobInTheDay; i++){
difficulty(jobDifficulty, i+1, currentDay+1, maxDay)
}This algorithm is the backbone of DFS, backtracking, and top-down implementation. They are all related concepts with somewhat very similar coding methods. The main idea is that:
- Use the for loop and its index to traverse horizontally.
- Use the recursive function call to traverse vertically, deeper to child nodes.
- Backtrack to parent node when the recursive function returns the result.
- On the next for loop iteration, traverse horizontally to the next branch, and continue.
The photo below illustrates how the program traverses along the decision tree. Note the order that the tree is travers would be along the blue arrows -> orange arrows -> red arrows -> blue arrows -> orange arrows, which correspond to the above 4 steps.
Space Complexity
- Space Complexity: since we create a cache array with the following
cache.resize(jobDifficulty.size(), vector<int>(d,-1))we have the space complexity as O(n*d) where n is the size of jobDifficulty array and d is the day
Time Complexity
At the core of the above algorithm is the for loop and the recursive call within the for loop when the index of the for loop is used as the argument of the recursive call. Thus, we would have the equivalent of double for loop as below:
for (int i = startingIndex; i <= maxNumberOfJobInTheDay; i++) {
difficulty(jobDifficulty, i+1, currentDay+1, maxDay);
}
// same as::
for (int i = startingIndex; i <= maxNumberOfJobInTheDay; i++) {
for (int j = i+1; i <= maxNumberOfJobInTheDay; j++)
// do something here;
}let n = maxNumberOfJobInTheDay,
For each iteration of the outer loop, the inner loop runs n-i iterations (since j starts from i+1). So the total number of iterations of the inner loop is:
(n-1) + (n-2) + ... + 1 = (n*(n-1))/2
Therefore, the time complexity for this algorithm is O(n)*O(n*(n-1))/2)=O(n^2)
But that doesn't end there; there is also "do something" operation. The operation takes d times. Overally we have O(n^2 * d) complexity.
Another way to think of the complexity is there are n*d possible states, and we need O(n) time to calculate the result for each state. Thus we have O(n^2 * d) complexity.
This algorithm is also called graph coloring problem, one of many backtracking algorithms. This problem has a general template code and a complexity as above.
References: