Posts tagged as “dp”

花花酱 LeetCode 1140. Stone Game II

By zxi on July 27, 2019

Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alex and Lee take turns, with Alex starting first. Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Constraints:

1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4

Solution: Recursion + Memoization

def solve(s, m) = max diff score between two players starting from s for the given M.

cache[s][M] = max{sum(piles[s:s+x]) – solve(s+x, max(x, M)}, 1 <= x <= 2*M, s + x <= n

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

// Author: Huahua, 12 ms / 9.7 MB

class Solution {

public:

int stoneGameII(vector<int>& piles) {

const int n = piles.size();

unordered_map<int, int> cache;

// Maximum diff starting from piles[s] given M.

function<int(int, int)> solve = [&](int s, int M) {

if (s >= n) return 0;

const int key = (s << 8) | M;

if (cache.count(key)) return cache[key];

int best = INT_MIN;

int curr = 0;

for (int x = 1; x <= 2 * M; ++x) {

if (s + x > n) break;

curr += piles[s + x - 1];

best = max(best, curr - solve(s + x, max(x, M)));

}

return cache[key] = best;

};

int total = accumulate(begin(piles), end(piles), 0);

return (total + solve(0, 1)) / 2;

}

};

花花酱 LeetCode 1139. Largest 1-Bordered Square

By zxi on July 27, 2019

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn’t exist in the grid.

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

Input: grid = [[1,1,0,0]]
Output: 1

Constraints:

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] is 0 or 1

Solution: DP

Compute the sums of all rectangles that has left-top corner at (0, 0) in O(m*n) time.
For each square and check whether its borders are all ones in O(1) time.

Time complexity: O(m*n*min(m,n))
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int largest1BorderedSquare(vector<vector<int>>& grid) {

int n = grid.size();

int m = grid[0].size();

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

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

for (int j = 1; j <= m; ++j)

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + grid[i - 1][j - 1];

for (int len = min(n, m); len > 0; --len)

for (int x1 = 1, x2 = x1 + len - 1; x2 <= m; ++x1, ++x2)

for (int y1 = 1, y2 = y1 + len - 1; y2 <= n; ++y1, ++y2)

if (getArea(x1, y1, x2, y1, dp) == len

&& getArea(x1, y1, x1, y2, dp) == len

&& getArea(x1, y2, x2, y2, dp) == len

&& getArea(x2, y1, x2, y2, dp) == len)

return len * len;

return 0;

}

private:

int getArea(int x1, int y1, int x2, int y2, const vector<vector<int>>& dp) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

}

};

花花酱 LeetCode 1137. N-th Tribonacci Number

By zxi on July 27, 2019

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of T_n.

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25
Output: 1389537

Constraints:

0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Solution: DP

Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++

// Author: Huahua

class Solution {

public:

int tribonacci(int n) {

if (n == 0) return n;

int t0 = 0;

int t1 = 1;

int t2 = 1;

int t = 1;

for (int i = 3; i <= n; ++i) {

t = t0 + t1 + t2;

t0 = t1;

t1 = t2;

t2 = t;

}

return t;

}

};

花花酱 1130. Minimum Cost Tree From Leaf Values

By zxi on July 20, 2019

Given an array arr of positive integers, consider all binary trees such that:

Each node has either 0 or 2 children;
The values of arr correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.)
The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.

Example 1:

Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.

    24            24
   /  \          /  \
  12   4        6    8
 /  \               / \
6    2             2   4

Constraints:

2 <= arr.length <= 40
1 <= arr[i] <= 15
It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

Solution: DP

dp[i][j] := answer of build a tree from a[i] ~ a[j]
dp[i][j] = min{dp[i][k] + dp[k+1][j] + max(a[i~k]) * max(a[k+1~j])} i <= k < j

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

class Solution {

public:

int mctFromLeafValues(vector<int>& arr) {

const int n = arr.size();

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

vector<vector<int>> m(n, vector<int>(n));

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

m[i][i] = arr[i];

for (int j = i + 1; j < n; ++j)

m[i][j] = max(m[i][j - 1], arr[j]);

}

for (int l = 2; l <= n; ++l)

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

int j = i + l - 1;

dp[i][j] = INT_MAX;

for (int k = i; k < j; ++k)

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + m[i][k] * m[k+1][j]);

}

return dp[0][n - 1];

}

};

花花酱 LeetCode 1125. Smallest Sufficient Team

By zxi on July 15, 2019

In a project, you have a list of required skills req_skills, and a list of people. The i-th person people[i] contains a list of skills that person has.

Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person: for example, team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].

Return any sufficient team of the smallest possible size, represented by the index of each person.

You may return the answer in any order. It is guaranteed an answer exists.

Example 1:

Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output: [0,2]

Example 2:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

Constraints:

1 <= req_skills.length <= 16
1 <= people.length <= 60
1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
Elements of req_skills and people[i] are (respectively) distinct.
req_skills[i][j], people[i][j][k] are lowercase English letters.
It is guaranteed a sufficient team exists.

Solution: DP

C++/Array

// Author: Huahua, 24 ms / 11 MB

class Solution {

public:

vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {

const int n = req_skills.size();

const int target = (1 << n) - 1;

vector<int> skills;

for (const auto& p : people) {

int mask = 0;

for (const string& s: p)

mask |= (1 << find(begin(req_skills), end(req_skills), s) - begin(req_skills));

skills.push_back(mask);

}

vector<int> dp((1 << n), INT_MAX / 2);

vector<pair<int, int>> pt((1 << n));

dp[0] = 0;

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

const int k = skills[i];

if (k == 0) continue;

for (int j = target; j >= 0; --j)

if (dp[j] + 1 < dp[j | k]) {

dp[j | k] = dp[j] + 1;

pt[j | k] = {j, i};

}

int t = target;

vector<int> ans;

while (t) {

ans.push_back(pt[t].second);

t = pt[t].first;

}

return ans;

}

};

C++/HashTable

// Author: Huahua, 272 ms / 94.8 MB

class Solution {

public:

vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {

const int n = req_skills.size();

vector<int> skills;

for (const auto& p : people) {

int mask = 0;

for (const string& s: p)

mask |= (1 << find(begin(req_skills), end(req_skills), s) - begin(req_skills));

skills.push_back(mask);

}

unordered_map<int, vector<int>> dp;

dp[0] = {};

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

unordered_map<int, vector<int>> tmp(dp);

for (const auto& kv : dp) {

int k = kv.first | skills[i];

if (!tmp.count(k) || kv.second.size() + 1 < tmp[k].size()) {

tmp[k] = kv.second;

tmp[k].push_back(i);

}

tmp.swap(dp);

}

return dp[(1 << n) - 1];

}

};