LeetCode 322. Coin Change (Iteration in the recurrence relation)

 322. Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

 

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

 

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

	class Solution {
	public:
	/**
	Framework(top-down) Iteration in the recurrence relation
	1. function
	i: min num of i coin
	dp(amount)
	2. relation
	dp[i] = min(dp(i - coin)) coin: avaible
	3. base
	dp(0) return 0
	*/
	int n;
	vector<int> con;
	vector<int> memo;
	int dp(int a){
	// base
	if(a == 0)
	return 0;
	if(memo[a] == 0){
	// iteration for each coin
	int res = INT_MAX;
	for(auto c: con){
	if(a >= c and dp(a - c) != -1)
	res = min(res, dp(a - c) + 1);
	}
	if(res == INT_MAX)
	memo[a] = -1;
	else
	memo[a] = res;
	}
	return memo[a];
	}
	int coinChange(vector<int>& coins, int amount) {
	// make global
	con = coins;
	memo.resize(amount + 1);
	return dp(amount);
	}
	};

view raw 322. Coin Change.cpp hosted with ❤ by GitHub

LeetCode 1335. Minimum Difficulty of a Job Schedule (Iteration in the recurrence relation)

1335. Minimum Difficulty of a Job Schedule

ref

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: 7
Explanation: 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 

Example 2:

Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

Example 3:

Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.

 

Constraints:

• 1 <= jobDifficulty.length <= 300
• 0 <= jobDifficulty[i] <= 1000
• 1 <= d <= 10

	class Solution {
	public:
	/**
	Framework (Top-Down: Memorization)
	1. function
	dp[i][day]: min diff, starts ith job, with day
	dp[0][1]: answer
	2. relation
	min(hardest + dp[i+1][j+1]), 1 < j < n - day
	3. base
	(day == d) max(jobs[i..])
	*/
	int D, n;
	vector<int> jobs;
	vector<int> hardestRemain;
	vector<vector<int>> memo;
	int dp(int i, int day){
	// base
	if(day == D)
	return hardestRemain[i];
	if(memo[i][day] == - 1){
	int limit = n - (D - day);
	int ans = 10001;
	int hardest = 0;
	for(int j = i; j < limit; j++){
	hardest = max(hardest, jobs[j]);
	ans = min(ans, dp(j + 1, day + 1) + hardest);
	}
	memo[i][day] = ans;
	}
	return memo[i][day];
	}
	int minDifficulty(vector<int>& jobDifficulty, int d) {
	// make global
	D = d;
	jobs = jobDifficulty;
	n = jobs.size();
	hardestRemain.resize(n);
	memo.resize(n+1, vector<int>(d+1, -1));
	// edge case
	if(d > n) return -1;
	// prepare hardest remain
	for(int i = n - 1; i >= 0; i--){
	hardestRemain[i] = jobs[i];
	if(i < n - 1) hardestRemain[i] = max(hardestRemain[i+1], hardestRemain[i]);
	}
	return dp(0, 1);
	}
	};

view raw 1335. Minimum Difficulty of a Job Schedule(memo).cpp hosted with ❤ by GitHub

LeetCode 221. Maximal Square

221. Maximal Square

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'.

	class Solution {
	public:
	/**
	Framework
	1. State & Function
	state vars: (i, j) i = ver, j = hor
	dp[row][col]: largest square, matrix[row][col] is square's right bottom corner
	2. Relation
	dp[i][j] = dp[i-1][j] == dp
	3. Base
	*/
	int maximalSquare(vector<vector<char>>& matrix) {
	int m = matrix.size();
	int n = matrix[0].size();
	vector<vector<int>> dp(m + 1, vector<int>(n + 1));
	int ans = 0;
	for(int i = 1; i <= m; i++){
	for(int j = 1; j <= n; j++){
	if(matrix[i-1][j-1] == '0')
	continue;
	// relation
	dp[i][j] = min({dp[i][j-1], dp[i-1][j], dp[i-1][j-1]}) + 1;
	// update ans
	ans = max(ans, dp[i][j] * dp[i][j]);
	}
	}
	return ans;
	}
	};

view raw 221. Maximal Square.cpp hosted with ❤ by GitHub

LeetCode 1143. Longest Common Subsequence

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

 

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

 

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

	class Solution {
	public:
	int longestCommonSubsequence(string text1, string text2) {
	// state var:
	// i: text1 index, j: text2 index
	// function:
	// dp(i, j): LCS of text1[0:i] text2[0:j] -> dp(len(t1), len(t2))
	// relation:
	// dp(i, j) = dp[i-1][j-1] + 1 (if text1[i] == text[j]) or max(dp[i-1][j], d[i][j-1])
	// base:
	// dp[0][x], dp[x][0] = 0
	// vars
	int n = text1.size();
	int m = text2.size();
	// memo
	vector<vector<int>> dp(n+1, vector<int>(m+1));
	// bottom-up
	for(int i = 1; i <= n; i++){
	for(int j = 1; j <= m; j++){
	// relation
	if(text1[i-1] == text2[j-1])
	dp[i][j] = dp[i-1][j-1] + 1;
	else
	dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
	}
	}
	// answer
	return dp[n][m];
	}
	};

view raw 1143. Longest Common Subsequence.cpp hosted with ❤ by GitHub

Multidimensional DP

State variables

The following are common things to look out for in DP problems that require a state variable:

• An index along some input.
  • input: nums = [0, 1, 2, 3, 4, 5, 6]
  • state: dp(4)
    -sub problem: nums = [0, 1, 2, 3]
• A second index along some input.
  • input: nums = [0, 1, 2, 3, 4, 5, 6]
  • state: dp(1, 3)
    • sub problem: nums = [1, 2, 3]
• Explicit numerical constraints given in the problem.
  • “you are only allowed to complete k transactions”,
  • “you are allowed to break up to k obstacles”, etc.
• Variables that describe statuses in a given state.
  • “true if currently holding a key, false if not”,
  • “currently holding k packages” etc.
• Some sort of data like a tuple or bitmask used to indicate things being “visited” or “used”.
  • For example, "bitmask is a mask where the i th bit indicates city has been visited".

Ref

• Multidimensional DP

LeetCode 740. Delete and Earn

740. Delete and Earn

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:

• Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.

Return the maximum number of points you can earn by applying the above operation some number of times.

 

Example 1:

Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.

Example 2:

Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.

 

Constraints:

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] <= 104

	class Solution {
	public:
	// Point: DP on input integer range!
	int deleteAndEarn(vector<int>& nums) {
	int nmax = 1e4 + 1;
	map<int, int> cnt;
	for(auto x: nums) cnt[x]++;
	vector<int> dp(nmax + 1);
	dp[0] = 0;
	dp[1] = cnt[1];
	for(int i = 2; i < nmax; i++){
	dp[i] = max(dp[i-1], dp[i-2] + cnt[i] * i);
	}
	return dp[nmax - 1];
	}
	};

view raw 740. Delete and Earn.cpp hosted with ❤ by GitHub

LeetCode 1064. Fixed Point

Problem

Given an array of distinct integers arr, where arr is sorted in ascending order, return the smallest index i that satisfies arr[i] == i. If there is no such index, return -1.

 

Example 1:

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

Example 2:

Input: arr = [0,2,5,8,17]
Output: 0
Explanation: arr[0] = 0, thus the output is 0.

Example 3:

Input: arr = [-10,-5,3,4,7,9]
Output: -1
Explanation: There is no such i that arr[i] == i, thus the output is -1.

 

Constraints:

• 1 <= arr.length < 104
• -109 <= arr[i] <= 109

 

Follow up: The O(n) solution is very straightforward. Can we do better?

	class Solution {
	public:
	int fixedPoint(vector<int>& arr) {
	int l = 0;
	int r = arr.size() - 1;
	while(l < r){
	int mid = (l + r) / 2;
	if(arr[mid]>=mid)
	r = mid;
	else
	l = mid + 1;
	}
	if(arr[l] == l) return l;
	return -1;
	}
	};

view raw 1064. Fixed Point.cpp hosted with ❤ by GitHub

Template: Answer on Binary Search

reference

PSUDO CODE-
-------------
int check(a,mid)
{
	// find answer using this mid
}
while(l<r)
{
	m = (l+r)/2;
	if(check(arr,m)>=givenK)
	//	move left or right accordingly
	else
	//	move left or right accordingly
} 
return ans;

 

LeetCode 2187. Minimum Time to Complete Trips

https://leetcode.com/problems/minimum-time-to-complete-trips/

	class Solution {
	public:
	// this function will count totalTrips for the given time
	// a = [1,2,3] , and at time 3 how many trips we can take?
	// 3/1 + 3/2 + 3/3 => 3 + 1 + 1 = 5 Trips
	long long int numberOfTripsForGivenTime(vector<int>&a , long long int givenTime)
	{
	long long int totalTrips = 0;
	for(auto x : a)
	{
	// convert it to long long int
	long long int val = x;
	totalTrips += (givenTime / val);
	}
	return totalTrips;
	}
	long long minimumTime(vector<int>& arr , int totalTrips) {
	long long int lowestTime = 1;
	long long int highestTime = 1e14;
	while(lowestTime<highestTime)
	{
	long long int mid = lowestTime + (highestTime-lowestTime)/2;
	if(numberOfTripsForGivenTime(arr , mid) >= totalTrips)
	highestTime = mid;
	else
	lowestTime = mid+1;
	}
	return lowestTime;
	}
	};

view raw 2187. Minimum Time to Complete Trips.cpp hosted with ❤ by GitHub

LeetCode 198. House Robber

 https://leetcode.com/problems/house-robber/

	class Solution {
	public:
	map<int, int> memo;
	vector<int> h;
	int dp(int i){
	// base
	if(i == 0)
	return h[i];
	if(i == 1)
	return max(h[0], h[1]);
	// use memo
	if(memo.find(i) != memo.end())
	return memo[i];
	// relation
	memo[i] = max(dp(i-1), dp(i-2) + h[i]);
	return memo[i];
	}
	int rob(vector<int>& nums) {
	h = nums;
	int n = nums.size();
	return dp(n - 1);
	}
	};

view raw 198. House Robber.cpp hosted with ❤ by GitHub

Framework for DP Problems

Framework for DP Problems

The Framework

1. A function or data structure that will compute/contain the answer to the problem for every given state.

2. A recurrence relation to transition between states.

3. Base cases, so that our recurrence relation doesn't go on infinitely.

Approach: Top-down and Bottom-up

Bottom-up (Tabulation)

// Pseudocode example for bottom-up

F = array of length (n + 1)
F[0] = 0
F[1] = 1
for i from 2 to n:
    F[i] = F[i - 1] + F[i - 2]

Top-down (Memoization)

// Pseudocode example for top-down

memo = hashmap
Function F(integer i):
    if i is 0 or 1: 
        return i
    if i doesn't exist in memo:
        memo[i] = F(i - 1) + F(i - 2)
    return memo[i]

Steps to convert top-down into bottom-up

1. Start with a completed top-down implementation.

2. Initialize an array $\text{dp}$ that is sized according to your state variables. For example, let's say the input to the problem was an array $\text{nums}$ and an integer $\text{k}$ that represents the maximum number of actions allowed. Your array $\text{dp}$ would be 2D with one dimension of length $\text{nums.length}$ and the other of length $\text{k}$. The values should be initialized as some default value opposite of what the problem is asking for. For example, if the problem is asking for the maximum of something, set the values to negative infinity. If it is asking for the minimum of something, set the values to infinity.

3. Set your base cases, same as the ones you are using in your top-down function. Recall in House Robber, $\text{dp(0) = nums[0]}$ and $\text{dp(1) = max(nums[0], nums[1])}$. In bottom-up, $\text{dp[0] = nums[0]}$ and $\text{dp[1] = max(nums[0], nums[1])}$.

4. Write a for-loop(s) that iterate over your state variables. If you have multiple state variables, you will need nested for-loops. These loops should start iterating from the base cases.

5. Now, each iteration of the inner-most loop represents a given state, and is equivalent to a function call to the same state in top-down. Copy the logic from your function into the for-loop and change the function calls to accessing your array. All $\text{dp(...)}$ changes into $\text{dp[...]}$.

6. We're done! $\text{dp}$ is now an array populated with the answer to the original problem for all possible states. Return the answer to the original problem, by changing $\text{return dp(...)}$ to $\text{return dp[...]}$.

When to Use DP

The first characteristic

that is common in DP problems is that the problem will ask for the optimum value (maximum or minimum) of something, or the number of ways there are to do something. For example:

• What is the minimum cost of doing...

• What is the maximum profit from...

• How many ways are there to do...

• What is the longest possible...

• Is it possible to reach a certain point...

The second characteristic

that is common in DP problems is that future "decisions" depend on earlier decisions. Deciding to do something at one step may affect the ability to do something in a later step. This characteristic is what makes a greedy algorithm invalid for a DP problem - we need to factor in results from previous decisions.

What is Dynamic Programming?

Dynamic Programming (DP) is a programming paradigm that can systematically and efficiently explore all possible solutions to a problem. As such, it is capable of solving a wide variety of problems that often have the following characteristics:

1. The problem can be broken down into "overlapping subproblems" - smaller versions of the original problem that are re-used multiple times.
2. The problem has an "optimal substructure" - an optimal solution can be formed from optimal solutions to the overlapping subproblems of the original problem.

Iteration in the recurrence relation

---

In all the problems we have looked at so far, the recurrence relation is a static equation - it never changes. Recall Min Cost Climbing Stairs. The recurrence relation was:

$\text{dp(i)} = \min( \text{dp(i - 1) + cost[i - 1], dp(i - 2) + cost[i - 2]})$

because we are only allowed to climb 1 or 2 steps at a time. What if the question was rephrased so that we could take up to $\text{k}$ steps at a time? The recurrence relation would become dynamic - it would be:

$\text{dp(i)} = \min( \text{dp(j) + cost[j])}$ for all $\text{(i - k)} \leq \text{j} < \text{i}$

We would need iteration in our recurrence relation.

This is a common pattern in DP problems, and in this chapter, we're going to take a look at some problems using the framework where this pattern is applicable. While iteration usually increases the difficulty of a DP problem, particularly with bottom-up implementations, the idea isn't too complicated. Instead of choosing from a static number of options, we usually add a for-loop to iterate through a dynamic number of options and choose the best one.

State Transition by Inaction

---

This is a small pattern that occasionally shows up in DP problems. Here, "doing nothing" refers to two different states having the same value. We're calling it "doing nothing" because often the way we arrive at a new state with the same value as the previous state is by "doing nothing" (we'll look at some examples soon). Of course, a decision making process needs to coexist with this pattern, because if we just had all states having the same value, the problem wouldn't really make sense ($\text{dp(i) = dp(i - 1)} ?$) It is just that if we are trying to maximize or minimize a score for example, sometimes the best option is to "do nothing", which leads to two states having the same value. The actual recurrence relation would look something like $\text{dp(i, j) = max(dp(i - 1, j), ...)}$.

Usually when we "do nothing", it is by moving to the next element in some input array (which we usually use $\text{i}$ as a state variable for). As mentioned above, this will be part of a decision making process due to some restriction in the problem. For example, think back to House Robber: we could choose to rob or not rob each house we were at. Sometimes, not robbing the house is the best decision (because we aren't allowed to rob adjacent houses), then $\text{dp(i) = dp(i - 1)}$.

In the next article, we'll use the framework to solve a problem with this pattern.

State Reduction

---

Note: state reductions for space complexity usually only apply to bottom-up implementations, while improving time complexity by reducing the number of state variables applies to both implementations.

When it comes to reducing state variables, it's hard to give any general advice or blueprint. The best advice is to try and think if any of the state variables are related to each other, and if an equation can be created among them. If a problem does not require iteration, there is usually some form of state reduction possible.

Whenever you notice that values calculated by a DP algorithm are only reused a few times and then never used again, try to see if you can save on space by replacing an array with some variables. A good first step for this is to look at the recurrence relation to see what previous states are used. For example, in Fibonacci, we only refer to the previous two states, so all results before $\text{n - 2}$ can be discarded.

Counting DP

---

Most of the problems we have looked at in earlier chapters ask for either the maximum, minimum, or longest of something. However, it is also very common for a DP problem to ask for the number of distinct ways to do something. In fact, one of the first examples we looked at did this - recall that Climbing Stairs asked us to find the number of ways to climb to the top of the stairs.

Another term used to describe this class of problems is "counting DP".

What are the differences with counting DP? With the maximum/minimum problems, the recurrence relation typically involves a $\text{max()}$ or $\text{min()}$ function. This is true for all types of problems we have looked at - iteration, multi-dimensional, etc. With counting DP, the recurrence relation typically just sums the results of multiple states together. For example, in Climbing Stairs, the recurrence relation was $\text{dp(i) = dp(i - 1) + dp(i - 2)}$. There is no $\text{max()}$ or $\text{min()}$, just addition.

Another difference is in the base cases. In most of the problems we have looked at, if the state goes out of bounds, the base case equals $\text{0}$. For example, in the Best Time to Buy and Sell Stock questions, when we ran out of transactions or ran out of days to trade, we returned $\text{0}$ because we can't make any more profit. In Longest Common Subsequence, when we run out of characters for either string, we return $\text{0}$ because the longest common subsequence of any string and an empty string is $\text{0}$. With counting DP, the base cases are often not set to $\text{0}$. This is because the recurrence relation usually only involves addition terms with other states, so if the base case was set to $\text{0}$ then you would only ever add $\text{0}$ to itself. Finding these base cases involves some logical thinking - for example, when we looked at Climbing Stairs - we reasoned that there is $\text{1}$ way to climb to the first step and $\text{2}$

$\text{2}$ ways to climb to the second step. 

Kadane's Algorithm

---

Kadane's Algorithm is an algorithm that can find the maximum sum subarray given an array of numbers in $O(n)$ time and $O(1)$ space. Its implementation is a very simple example of dynamic programming, and the efficiency of the algorithm allows it to be a powerful tool in some DP algorithms. If you haven't already solved Maximum Subarray, take a quick look at the problem before continuing with this article - Kadane's Algorithm specifically solves this problem.

Kadane's Algorithm involves iterating through the array using an integer variable $\text{current}$, and at each index $\text{i}$, determines if elements before index $\text{i}$ are "worth" keeping, or if they should be "discarded". The algorithm is only useful when the array can contain negative numbers. If $\text{current}$ becomes negative, it is reset, and we start considering a new subarray starting at the current index.

Pseudocode for the algorithm is below:

// Given an input array of numbers "nums",
1. best = negative infinity
2. current = 0
3. for num in nums:
    3.1. current = Max(current + num, num)
    3.2. best = Max(best, current)

4. return best

Line 3.1 of the pseudocode is where the magic happens. If $\text{current}$ has become less than 0 from including too many or too large negative numbers, the algorithm "throws it away" and resets.

While usage of Kadane's Algorithm is a niche, variations of Kadane's Algorithm can be used to develop extremely efficient DP algorithms. Try the next two practice problems with this in mind. No framework hints are provided here as implementations of Kadane's Algorithm do not typically follow the framework intuitively, although they are still technically dynamic programming (Kadane's Algorithm utilizes optimal sub-structures - it keeps the maximum subarray ending at the previous position in $\text{current}$).