Minimum (Maximum) Path to Reach a Target¶
Given a target find minimum (maximum) cost / path / sum to reach the target.
0746. Min Cost Climbing Stairs¶
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
Example 1:
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
Constraints:
2 <= cost.length <= 10000 <= cost[i] <= 999
dp[i] min cost to reach ith stair.
for (int i = 2; i <= n; ++i) {
// on last step, there is no need to proceed further.
dp[i] = min(dp[i-1], dp[i-2]) + (i == n ? 0 : cost[i]);
}
return dp[n]
with optimization
int p1 = 0, p2 = 0;
for (int i = 2; i <= cost.size(); ++i) {
int p = min(p1 + cost[i - 1], p2 + cost[i - 2]);
p2 = p1;
p1 = p;
}
return p1;
0064. Minimum Path Sum¶
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
dp[i][j]: min sum to reach x=i,y=j, dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j]
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
}
}
return grid[n-1][m-1]
0322. 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 <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
dp[j]: min # of coins to be used for j amount
for (int j = 1; j <= amount; ++j) {
for (int i = 0; i < coins.size(); ++i) { // try all coins
if (coins[i] <= j) { // only try the one that is less than total required
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount];
Why this cannot be solved by greedy algorithm?¶
Exception:
But for some coin sets, there are sums for which the greedy algorithm fails. For example, for the set {1, 15, 25} and the sum 30, the greedy algorithm first chooses 25, leaving a remainder of 5, and then five 1s for a total of six coins. But the solution with the minimal number of coins is to choose 15 twice.
In any case where there is no coin whose value, when added to the lowest denomination, is lower than twice that of the denomination immediately less than it, the greedy algorithm works. i.e. {1,2,3} works because [1,3] and [2,2] add to the same value however {1, 15, 25} doesn't work because (for the change 30) 15+15>25+1
0931. Minimum Falling Path Sum¶
Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.
A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).
Example 1:
Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.
Example 2:
Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.
Constraints:
n == matrix.length == matrix[i].length1 <= n <= 100-100 <= matrix[i][j] <= 100
A[i][j]: min sum from all upper level to current level i and position j, to get the ans, just find the min on the last row
int minFallingPathSum(vector<vector<int>>& A) {
int m = A.size(), n = A[0].size();
int res = INT_MAX;
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
A[i][j] += min(
{A[i - 1][j], A[i - 1][max(0, j - 1)], A[i - 1][min(m - 1, j + 1)]});
}
}
for (int i = 0; i < n; ++i) res = min(res, A[m - 1][i]);
return res;
}
0983. Minimum Cost For Tickets¶
You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.
Train tickets are sold in three different ways:
- a 1-day pass is sold for
costs[0]dollars, - a 7-day pass is sold for
costs[1]dollars, and - a 30-day pass is sold for
costs[2]dollars.
The passes allow that many days of consecutive travel.
- For example, if we get a 7-day pass on day
2, then we can travel for7days:2,3,4,5,6,7, and8.
Return the minimum number of dollars you need to travel every day in the given list of days.
Example 1:
Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.
Example 2:
Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total, you spent $17 and covered all the days of your travel.
Constraints:
1 <= days.length <= 3651 <= days[i] <= 365daysis in strictly increasing order.costs.length == 31 <= costs[i] <= 1000
dp[i]: min cost for ith day. Note: if there is no travel plan, the cost will stay the same as the i-1 th day.
int mincostTickets(vector<int>& days, vector<int>& costs) {
unordered_set<int> travel(begin(days), end(days));
int dp[366] = {};
for (int i = 1; i < 366; ++i) {
if (travel.find(i) == travel.end()) dp[i] = dp[i - 1];
else dp[i] = min({ dp[i - 1] + costs[0], dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2]});
}
return dp[365];
}
0650. 2 Keys Keyboard¶
There is only one character 'A' on the screen of a notepad. You can perform two operations on this notepad for each step:
- Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
- Paste: You can paste the characters which are copied last time.
Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.
Example 1:
Input: n = 3
Output: 3
Explanation: Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.
Example 2:
Input: n = 1
Output: 0
Constraints:
1 <= n <= 1000
dp[i]: min steps to get to get i 'A' characters.
int dp[n + 1];
memset(dp, 0, sizeof dp);
for (int i = 2; i <= n; ++i) {
dp[i] = i; // initially assume copy one and paste one by one
for (int j = i - 1; j >= 1; --j) {
if (i % j == 0) {
dp[i] = dp[j] + i / j; // j is the maximum, so no need to check the rest
break;
}
}
}
return dp[n];
Optimize
int s = 0;
for (int d = 2; d <= n; d++) {
while (n % d == 0) {
s += d;
n /= d;
}
}
return s;
0279. Perfect Squares¶
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
Constraints:
1 <= n <= 10^4
dp[i]: min # of perfect squares to form i
int numSquares(int n) {
int dp[n + 1], inf = 0x3f3f3f3f;
memset(dp, inf, sizeof dp);
for (int i = 0; i <= n; ++i) {
for (int j = 1; j * j <= i; ++j) {
if (i - j * j >= 0) dp[i] = min(dp[i], dp[i - j * j] + 1);
if (j * j == i) dp[i] = 1;
}
}
return dp[n];
}
1049. Last Stone Weight II¶
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
- If
x == y, both stones are destroyed, and - If
x != y, the stone of weightxis destroyed, and the stone of weightyhas new weighty - x.
At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left stone. If there are no stones left, return 0.
Example 1:
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.
Example 2:
Input: stones = [31,26,33,21,40]
Output: 5
Constraints:
1 <= stones.length <= 301 <= stones[i] <= 100
int lastStoneWeightII(vector<int>& stones) {
int n = stones.size(), sum = 0;
for (int s : stones) sum += s;
vector<bool> dp(sum + 1, false);
dp[0] = true;
for (int i = 0; i < n; ++i) {
for (int j = sum / 2; j >= stones[i]; --j)
dp[j] = dp[j] | dp[j - stones[i]];
}
for (int i = sum / 2; i >= 0; --i)
if (dp[i]) return sum - i - i;
return sum;
}
0120. Triangle¶
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Example 1:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
Example 2:
Input: triangle = [[-10]]
Output: -10
Constraints:
1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104
Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?
dp[i]: min cost from bottom to i-th row
int minimumTotal(vector<vector<int>>& triangle) {
vector<int> dp(triangle.back());
int n = triangle.size();
for (int i = n - 2; i >= 0; --i) { // rows
for (int j = 0; j <= i; ++j) { // num of elem in each row = i + 1
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]; // left: dp[j], right: dp[j + 1]
}
}
return dp[0];
}
0474. Ones and Zeroes¶
You are given an array of binary strings strs and two integers m and n.
Return *the size of the largest subset of strs such that there are at most* m 0's and n 1's in the subset.
A set x is a subset of a set y if all elements of x are also elements of y.
Example 1:
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
Example 2:
Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.
Constraints:
1 <= strs.length <= 6001 <= strs[i].length <= 100strs[i]consists only of digits'0'and'1'.1 <= m, n <= 100
My dp[i][j] means with i zeros and j ones, what is the max strings to be chosen from the strs. In order to calculate it, we find there is a relationship between # of 1 and 0, which is # of 1 + # of 0 = string size, this pattern of constraint usually leads to a knapsack problem. We can visualize it with the problem of knapsack:
- choose current string means dp[i-# of zero for current string][j - # of one for current string] + 1.
- not choose current string means dp[i][j] which means there is nothing changed as previous state. Why it has to start from m, n and decrease to 1 (or making sure there is at least # of 0 or 1 spots left in our case)? Because it prevents invalid counting. As we can see, our dp[m][n] is going to be updated sz times, and before we calculate i - zero[k] and j - one[k], they has to be valid. If we start from 0 and increase to m, n, these values will never be updated beforehand.
int findMaxForm(vector<string>& strs, int m, int n) {
int sz = strs.size();
int one[sz], zero[sz];
for (int i = 0; i < sz; ++i) {
int c1 = 0, c2 = 0;
for (char c : strs[i]) {
if (c == '1') c2++;
if (c == '0') c1++;
}
zero[i] = c1, one[i] = c2;
}
int dp[m + 1][n + 1];
memset(dp, 0, sizeof dp);
for (int k = 0; k < sz; ++k) {
for (int i = m; i >= zero[k]; --i) {
for (int j = n; j >= one[k]; --j) {
dp[i][j] = max(dp[i][j], dp[i - zero[k]][j - one[k]] + 1);
}
}
}
return dp[m][n];
}
0221. 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.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]is'0'or'1'.
Here thedp[i][j]the same as matrix[i][j], and it means the maximum width of the square that includes matrix[i][j] as the right down side of the resulting square. To expand the area to any directions (right, down), we check the matrix[i][j-1], matrix[i-1][j] and matrix[i-1][j-1] and choose the minimal from them. The final answer is the maximum matrix[i][j] * matrix[i][j] from all the values we have filled.
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '0' || i == 0 || j == 0) continue;
matrix[i][j] = min({matrix[i][j - 1] - '0',
matrix[i - 1][j] - '0',
matrix[i - 1][j - 1] - '0'}) + '1';
res = max(res, matrix[i][j] - '0');
}
}
return res * res;