Dynamic Programming
GeeksforGeeks
https://www.geeksforgeeks.org/dynamic-programming/
https://www.geeksforgeeks.org/dynamic-programming-trees-set-1/
Problem Characteristics
Overlapping Subproblems
- Top down (recursive + memorization)
- Bottom up (tabulization)
Optimal Substructure
A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.
Classic 0-1 Knapsack Problem
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).
Time Complexity: O(nW) where n is the number of items and W is the capacity of knapsack. It is essentially the number of table entries to fill.
Divide & Conquer DP
Have to split the problem into two subproblems, and the nature is usually nested.
Some variations in the formulation / definition / meaning of the index k we chose to split:
- ballon k is the last to burst. 312. Burst Balloons
Fill Solution Table
Strategy to iteratively fill divide and conquer style dp solution table. It is base on the idea that the range length k=4 will use answers in range length k<4 (so they should be computed before k=4).
for (int k = 2; k < n; ++k) //start value of k depends on the problem
for (int left = 0; left < n - k; ++left) {
int right = left + k;
for (int i = left + 1; i < right; ++i)
dp[left][right] = Math.max(dp[left][right],
nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
}
Meaningful initialisation can simply the problem set up:
..... Initially, you are in the city indexed 0 on Monday ....
In this case, we initialise the dp table to Integer.MIN_VALUE, but set the starting city to 0. This essentially ensures those can start at city 0 will always give the answer of max vacation days.
public int maxVacationDays(int[][] flights, int[][] days) {
int n = days.length, k=days[0].length;
int[] maxVacation = new int[n];
Arrays.fill(maxVacation, Integer.MIN_VALUE);
maxVacation[0] = 0; // this ensure the starting point will be at city 0;
for(int v=0; v<k; v++) {
int[] temp = new int[n];
Arrays.fill(temp, Integer.MIN_VALUE);
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(i==j || flights[i][j]==1) {
temp[j] = Math.max(temp[j], maxVacation[i] + days[j][v]);
}
}
}
maxVacation = temp;
}
int maxDays = 0;
for(int vacation: maxVacation) {
maxDays = Math.max(maxDays, vacation);
}
return maxDays;
}
Wood-Cutting Style with Co-recursion
Something, we might have to deal with different states for a given subproblem. It is very likely we have to set up co-recursion equations.
309. Best Time to Buy and Sell Stock with Cooldown
State of take / not take:
Min of Max
There is another style of DP problem is, we want to calculate the minimum cost of something. But when we calculate the cost, we have to take the worst case if we want a sure win.
375. Guess Number Higher or Lower II
We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower. However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
class Solution {
public int getMoneyAmount(int n) {
int[][] cost = new int[n+1][n+1];
return calCost(cost, 1, n);
}
public int calCost(int[][] cost, int i, int j) {
if(i>=j) return 0;
if(cost[i][j]!=0) return cost[i][j];
int minCost = Integer.MAX_VALUE;
for(int k=i; k<=j; k++) {
minCost = Math.min(minCost, k + Math.max(calCost(cost, i, k-1), calCost(cost, k+1, j)));
}
cost[i][j] = minCost;
return cost[i][j];
}
}
Gradually Relaxing the Restriction
The approach to this problem is... for given length of array, k groups partition will generate a larger sum than the k-1 groups of partition. When we calculate the at most k groups partition sum, we need the k-1 groups partition result. So, iteratively calculate from k=1 to k=K.
We partition a row of numbersA into at mostKadjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?
Note that our partition must use every number in A, and that scores are not necessarily integers.
Example:
Input:
A = [9,1,2,3,9]
K = 3
Output:
20
Explanation:
The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.
Counting Related
750. Number Of Corner Rectangles
When you previously having x different corner rectangles, you add one pair of corner at the bottom, that additional pair could bring x+1 different corner rectangles.
o o
o o //can form additional 1
o o //can form additional 2
o o //here you could form additional 3 corner rect
Given a grid where each entry is only 0 or 1, find the number of corner rectangles.
A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle.
Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.
Example 1:
Input: grid =
[[1, 0, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
[1, 0, 1, 0, 1]]
Output: 1
Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].
Counting Related -- Double Count
https://vjudge.net/problem/1162853/origin
A partition of an integernnis a set of positive integers which sum tonn, typically written in descending order. For example:
10 = 4+3+2+1
A partition ismm-ary if each term in the partition is a power ofmm. For example, the33-ary partitions of99are:
9
3+3+3
3+3+1+1+1
3+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1
Write a program to find the number ofmm-ary partitions of an integer n.
In this problem, we have to take care of double count scenario e.g. 3, 9 vs 9,3 .... sometimes we could apply a restriction to avoid it e.g. the factors that make up the number shouldn't be >= 3 (3, 9 case): since the list of number is strictly increasing...
1+1+1.... will not be considered in dp, every number can be in this form... so by default, every number will dp[num] = 1
import java.util.*;
public class MAryPartitions {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int nc = sc.nextInt();
for(int i=0; i<nc; i++) {
int caseNum = sc.nextInt();
int m = sc.nextInt();
int num = sc.nextInt();
int lookup[] = new int[num];
System.out.println(caseNum + " " + findMAryPartitions(num, m));
}
}
public static int findMAryPartitions(int num, int m) {
List<Integer> powers = new ArrayList<>();
powers.add(1);
for(int i=1; Math.pow(m, i)<=num; i++) {
powers.add(powers.get(powers.size()-1)*m);
}
int dp[] = new int[num+1];
Arrays.fill(dp, 1);
for(int i=1; i<powers.size(); i++) {
for(int j=0; j<num; j++) {
if(j+powers.get(i)>num) break;
dp[j+powers.get(i)] += dp[j];
System.out.println(j + " " + dp[j+powers.get(i)]);
}
}
return dp[num];
}
}
Trivial
Memorization
We usually use variables, 1d array or 2d array to do solution lookup. But sometimes we might need to look up based on other key format, for example, a list. We have to make sure the same list is hashed to the same key.
Max, Min
We don't want to write some complex if, we could utilise Math.max, min, even use them nested.
maxSqAt[i][j] = Math.min(maxSqAt[i-1][j-1], Math.min(maxSqAt[i-1][j], maxSqAt[i][j-1])) + 1;
Multiple States for a Given Position
Some dp problems are having multiple situations/states/scenarios to be stored / reused for a given i,j.
562. Longest Line of Consecutive One in Matrix
*For some dp problem involving matrix, if we use 1 dimension space and a prev variable, don't forget to update previous and the value in the 1d solution array even for the 'supposed to be skipped cells'. For example, we still need to update some values for below '0' values in the matrix.
Input:
[[0,1,1,0],
[0,1,1,0],
[0,0,0,1]]
Output: 3
Example of Space Optimization
The ith content only depends on the i-1th content, we can just use 1-d array, just read + calculation and then update into the original dp[].
class Solution {
public int change(int amount, int[] coins) {
/* int[][] numComb = new int[coins.length+1][amount+1];
numComb[0][0] = 1;
for(int i=1; i<=coins.length; i++) {
numComb[i][0] = 1;
for(int j=1; j<=amount; j++) {
numComb[i][j] = numComb[i-1][j] + (j-coins[i-1]>=0? numComb[i][j-coins[i-1]]: 0);
}
}
return numComb[coins.length][amount];*/
int[] numComb = new int[amount+1];
numComb[0] = 1;
for(int i=0; i<coins.length; i++) {
//don't need to start from amt 1 because we now use 1-d dp,
//so the values are there for dp[j] where j<the amount of the count
for(int j=coins[i]; j<=amount; j++) {
numComb[j] += numComb[j-coins[i]];// same as numComb[j] = numComb[j] (prev dp [i-1]) + numComb[j-coins[i]];
}
}
return numComb[amount];
}
}
Be mindful about the indexing
Due to dp array index shift by 1, the index i-1 is corresponding to the right index in the original nums array.
boolean[][] dp = new boolean[nums.length+1][sum+1];
dp[0][0] = true; //by default other values are false
for(int i=1; i<=nums.length; i++) {
for(int s=0; s<=subsetSum; s++) {
dp[i][s] = dp[i-1][s] || (s>=nums[i-1]? dp[i-1][s-nums[i-1]] : false);
}
}