Posts published in “Dynamic Programming”

花花酱 LeetCode 1449. Form Largest Integer With Digits That Add up to Target

By zxi on May 18, 2020

Given an array of integers cost and an integer target. Return the maximum integer you can paint under the following rules:

The cost of painting a digit (i+1) is given by cost[i] (0 indexed).
The total cost used must be equal to target.
Integer does not have digits 0.

Since the answer may be too large, return it as string.

If there is no way to paint any integer given the condition, return “0”.

Example 1:

Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: "7772"
Explanation:  The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 2*3+ 3*1 = 9. You could also paint "997", but "7772" is the largest number.
Digit    cost
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

Example 2:

Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: "85"
Explanation: The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost("85") = 7 + 5 = 12.

Example 3:

Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: "0"
Explanation: It's not possible to paint any integer with total cost equal to target.

Example 4:

Input: cost = [6,10,15,40,40,40,40,40,40], target = 47
Output: "32211"

Constraints:

cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000

Solution: DP

dp(target) := largest number to print with cost == target.
dp(target) = max(dp(target – d) + cost[d])

Time complexity: O(target^2)
Space complexity: O(target^2)

C++ / Top Down

// Author: Huahua, 280 ms

class Solution {

public:

string largestNumber(vector<int>& cost, int target) {

vector<string> cache(target + 1);

// dp[i] := largestNumber that has cost i.

function<string(int)> dp = [&](int t) -> string {

if (t < 0) return "0"; // Invalid.

if (t == 0) return ""; // Found a solution.

if (!cache[t].empty()) return cache[t];

cache[t] = "0"; // Important !!!

for (int d = 1; d <= 9; ++d) {

const string& cur = dp(t - cost[d - 1]);

if (cur != "0" && cur.length() + 1 >= cache[t].length())

cache[t] = to_string(d) + cur;

}

return cache[t];

};

return dp(target);

}

};

C++ / Bottom Up

// Author: Huahua, 240 ms

class Solution {

public:

string largestNumber(vector<int>& cost, int target) {

// dp[i] := largestNumber that has cost i.

vector<string> dp(target + 1, "0");

dp[0] = "";

for (int t = 1; t <= target; ++t)

for (int d = 1; d <= 9; ++d) {

const int s = t - cost[d - 1];

if (s < 0 || dp[s] == "0"

|| dp[s].length() + 1 < dp[t].length()) continue;

dp[t] = to_string(d) + dp[s];

}

return dp[target];

}

};

To avoid string copying, we can store digit added (in order to back track the parent) and length of the optimal string.

Time complexity: O(target)
Space complexity: O(target)

C++ / O(target)

// Author: Huahua, 25 ms

class Solution {

public:

string largestNumber(vector<int>& cost, int target) {

vector<pair<int, int>> cache(target + 1, {-1, -1});

// dp[i] := {digit, length} of largestNumber that has cost i.

function<pair<int, int>(int)> dp = [&](int t) -> pair<int, int> {

if (t < 0) return {0, -1}; // Invalid.

if (t == 0) return {0, 0}; // Found a solution.

if (cache[t].first != -1) return cache[t];

cache[t] = {0, -1}; // make as solved but invalid.

for (int d = 1; d <= 9; ++d) {

const int l = dp(t - cost[d - 1]).second;

if (l != -1 && l + 1 >= cache[t].second)

cache[t] = {d, l + 1};

}

return cache[t];

};

dp(target);

if (cache[target].second <= 0) return "0";

string ans;

while (target) {

ans += cache[target].first + '0';

target -= cost[cache[target].first - 1];

}

return ans;

}

};

C++ / O(target)

// Author: Huahua, 28 ms

class Solution {

public:

string largestNumber(vector<int>& cost, int target) {

// dp[i] = {d, length} of the largest number that costs i.

vector<pair<int, int>> dp(target + 1, {-1, -1});

dp[0] = {0, 0};

for (int t = 1; t <= target; ++t)

for (int d = 1; d <= 9; ++d) {

const int s = t - cost[d - 1];

if (s < 0 || dp[s].second == -1

|| dp[s].second + 1 < dp[t].second) continue;

dp[t] = {d, dp[s].second + 1};

}

if (dp[target].second == -1) return "0";

string ans;

while (target) {

ans += dp[target].first + '0';

target -= cost[dp[target].first - 1];

}

return ans;

}

};

花花酱 LeetCode 1444. Number of Ways of Cutting a Pizza

By zxi on May 15, 2020

Given a rectangular pizza represented as a rows x cols matrix containing the following characters: 'A' (an apple) and '.' (empty cell) and given the integer k. You have to cut the pizza into k pieces using k-1 cuts.

For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.

Return the number of ways of cutting the pizza such that each piece contains at least one apple. Since the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:

Input: pizza = ["A..","AAA","..."], k = 3
Output: 3 
Explanation: The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.

Example 2:

Input: pizza = ["A..","AA.","..."], k = 3
Output: 1

Example 3:

Input: pizza = ["A..","A..","..."], k = 1
Output: 1

Constraints:

1 <= rows, cols <= 50
rows == pizza.length
cols == pizza[i].length
1 <= k <= 10
pizza consists of characters 'A' and '.' only.

Solution: DP

dp(n, m, k) := # of ways to cut pizza[n:N][m:M] with k cuts.

dp(n, m, k) = sum(hasApples(n, m, N – 1, y) * dp(y + 1, n, k – 1) for y in range(n, M)) + sum(hasApples(n, m, x, M – 1) * dp(m, x + 1, k – 1) for x in range(n, M))

Time complexity: O(M*N*(M+N)*K) = O(N^3 * K)
Space complexity: O(M*N*K)

C++

// Author: Huahua

class Solution {

public:

int ways(vector<string>& pizza, int K) {

constexpr int kMod = 1e9 + 7;

const int M = pizza.size();

const int N = pizza[0].size();

vector<vector<int>> A(M + 1, vector<int>(N + 1));

for (int y = 0; y < M; ++y)

for (int x = 0; x < N; ++x)

A[y + 1][x + 1] = A[y + 1][x] + A[y][x + 1] + (pizza[y][x] == 'A') - A[y][x];

auto hasApples = [&](int x1, int y1, int x2, int y2) {

return (A[y2 + 1][x2 + 1] - A[y2 + 1][x1] - A[y1][x2 + 1] + A[y1][x1]) > 0;

};

vector<vector<vector<int>>> cache(M, vector<vector<int>>(N, vector<int>(K, -1)));

// dp(m, n, k) := # of ways to cut pizza[m:M][n:N] with k cuts.

function<int(int, int, int)> dp = [&](int m, int n, int k) -> int {

if (k == 0) return hasApples(n, m, N - 1, M - 1);

int& ans = cache[m][n][k];

if (ans != -1) return ans;

ans = 0;

for (int y = m; y < M - 1; ++y) // Cut horizontally.

ans = (ans + hasApples(n, m, N - 1, y) * dp(y + 1, n, k - 1)) % kMod;

for (int x = n; x < N - 1; ++x) // Cut vertically.

ans = (ans + hasApples(n, m, x, M - 1) * dp(m, x + 1, k - 1)) % kMod;

return ans;

};

return dp(0, 0, K - 1);

}

};

花花酱 LeetCode 1434. Number of Ways to Wear Different Hats to Each Other

By zxi on May 3, 2020

There are n people and 40 types of hats labeled from 1 to 40.

Given a list of list of integers hats, where hats[i] is a list of all hats preferred by the i-th person.

Return the number of ways that the n people wear different hats to each other.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

Example 2:

Input: hats = [[3,5,1],[3,5]]
Output: 4
Explanation: There are 4 ways to choose hats
(3,5), (5,3), (1,3) and (1,5)

Example 3:

Input: hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
Output: 24
Explanation: Each person can choose hats labeled from 1 to 4.
Number of Permutations of (1,2,3,4) = 24.

Example 4:

Input: hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]
Output: 111

Constraints:

n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] contains a list of unique integers.

Solution: DP

dp[i][j] := # of ways using first i hats, j is the bit mask of people wearing hats.

e.g. dp[3][101] == # of ways using first 3 hats that people 1 and 3 are wearing hats.

init dp[0][0] = 1

dp[i][mask | (1 << p)] = dp[i-1][mask | (1 << p)] + dp[i-1][mask], where people p prefers hats i.

ans: dp[nHat][1…1]

Time complexity: O(2^n * h * n)
Space complexity: O(2^n * h) -> O(2^n)

C++

// Author: Huahua

class Solution {

public:

int numberWays(vector<vector<int>>& hats) {

constexpr int kHat = 40;

constexpr int kMod = 1e9 + 7;

const int n = hats.size();

vector<vector<int>> people(kHat + 1); // hat -> {people}

for (int i = 0; i < n; ++i)

for (int hat : hats[i])

people[hat].push_back(i);

// dp[i][j] := # of ways using first i hats where j is bit mask of people wearing hats.

vector<vector<int>> dp(kHat + 1, vector<int>(1 << n));

dp[0][0] = 1;

for (int i = 1; i <= kHat; ++i) {

dp[i] = dp[i - 1];

for (int mask = (1 << n) - 1; mask >= 0; --mask)

for (int p : people[i]) {

if (mask & (1 << p)) continue;

dp[i][mask | (1 << p)] += dp[i - 1][mask];

dp[i][mask | (1 << p)] %= kMod;

}

return dp.back().back();

}

};

O(2^n) memory

C++

// Author: Huahua

class Solution {

public:

int numberWays(vector<vector<int>>& hats) {

constexpr int kHat = 40;

constexpr int kMod = 1e9 + 7;

const int n = hats.size();

vector<vector<int>> people(kHat + 1); // hat -> {people}

for (int i = 0; i < n; ++i)

for (int hat : hats[i])

people[hat].push_back(i);

// dp([i])[j] := # of ways using first i hats where j is bit mask of people wearing hat.

vector<int> dp(1 << n);

dp[0] = 1;

for (int i = 1; i <= kHat; ++i)

for (int mask = (1 << n) - 1; mask >= 0; --mask)

for (int p : people[i]) {

if (mask & (1 << p)) continue;

dp[mask | (1 << p)] += dp[mask];

dp[mask | (1 << p)] %= kMod;

}

return dp.back();

}

};

花花酱 LeetCode 1425. Constrained Subset Sum

By zxi on April 26, 2020

Given an integer array nums and an integer k, return the maximum sum of a non-empty subset of that array such that for every two consecutive integers in the subset, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subset of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subset is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subset must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subset is [10, -2, -5, 20].

Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Solution: DP / Sliding window / monotonic queue

dp[i] := max sum of a subset that include nums[i]
dp[i] := max(dp[i-1], dp[i-2], …, dp[i-k-1], 0) + nums[i]

C++

// Author: Huahua

class Solution {

public:

int constrainedSubsetSum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> dp(n);

multiset<int> s{INT_MIN};

int ans = INT_MIN;

for (int i = 0; i < nums.size(); ++i) {

if (i > k) s.erase(s.equal_range(dp[i - k - 1]).first);

dp[i] = max(*rbegin(s), 0) + nums[i];

s.insert(dp[i]);

ans = max(ans, dp[i]);

}

return ans;

}

};

Use a monotonic queue to track the maximum of a sliding window dp[i-k-1] ~ dp[i-1].

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua 184 ms

class Solution {

public:

int constrainedSubsetSum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> dp(n);

deque<int> q;

int ans = INT_MIN;

for (int i = 0; i < nums.size(); ++i) {

if (i > k && q.front() == i - k - 1)

q.pop_front();

dp[i] = (q.empty() ? 0 : max(dp[q.front()], 0))

+ nums[i];

while (!q.empty() && dp[i] >= dp[q.back()])

q.pop_back();

q.push_back(i);

ans = max(ans, dp[i]);

}

return ans;

}

};

花花酱 LeetCode 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

By zxi on April 20, 2020

Given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:

You should build the array arr which has the following properties:

arr has exactly n integers.
1 <= arr[i] <= m where (0 <= i < n).
After applying the mentioned algorithm to arr, the value search_cost is equal to k.

Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

Example 2:

Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisify the mentioned conditions.

Example 3:

Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]

Example 4:

Input: n = 50, m = 100, k = 25
Output: 34549172
Explanation: Don't forget to compute the answer modulo 1000000007

Example 5:

Input: n = 37, m = 17, k = 7
Output: 418930126

Constraints:

1 <= n <= 50
1 <= m <= 100
0 <= k <= n

Solution: DP

dp[n][m][k] := ways to build given n,m,k.

dp[n][m][k] = sum(dp[n-1][m][k] + dp[n-1][i-1][k-1] – dp[n-1][i-1][k]), 1 <= i <= m
dp[1][m][1] = m
dp[n][m][k] = 0 if k < 1 or k > m or k > n

Time complexity: O(n*m^2*k)
Space complexity: O(n*m*k)

C++

// Author: Huahua

int mem[51][101][51] = {0};

class Solution {

public:

int numOfArrays(int n, int m, int k) {

const int kMod = 1e9 + 7;

function<int(int, int, int)> dp = [&dp](int n, int m, int k) {

if (k < 1 || k > m || k > n) return 0;

if (n == 1 && k == 1) return m;

if (mem[n][m][k]) return mem[n][m][k];

long ans = 0;

for (int i = 1; i <= m; ++i) {

ans += dp(n - 1, m, k);

ans += dp(n - 1, i - 1, k - 1);

ans -= dp(n - 1, i - 1, k);

ans = (ans + kMod) % kMod;

}

return mem[n][m][k] = ans;

};

return dp(n, m, k);

}

};