Dynamic Programming Archives - Page 25 of 42

花花酱 LeetCode 1092. Shortest Common Supersequence

By zxi on June 16, 2019

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them.

(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywherefrom T) results in the string S.)

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a substring of "cabac" because we can delete the first "c".
str2 = "cab" is a substring of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

Note:

1 <= str1.length, str2.length <= 1000
str1 and str2 consist of lowercase English letters.

Solution: LCS

Find the LCS (longest common sub-sequence) of two strings, and insert unmatched characters into the LCS.

Time complexity: O(mn)
Space complexity: O(mn)

C++

// Author: Huahua, running time: 16 ms, 15.3 MB

class Solution {

public:

string shortestCommonSupersequence(string str1, string str2) {

int l1 = str1.length();

int l2 = str2.length();

vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));

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

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

dp[i][j] = str1[i - 1] == str2[j - 1] ?

1 + dp[i - 1][j - 1] :

max(dp[i - 1][j], dp[i][j - 1]);

deque<char> ans;

while (l1 || l2) {

char c;

if (l1 == 0) c = str2[--l2];

else if (l2 == 0) c = str1[--l1];

else if (str1[l1 - 1] == str2[l2 - 1]) c = str1[--l1] = str2[--l2];

else if (dp[l1 - 1][l2] == dp[l1][l2]) c = str1[--l1];

else if (dp[l1][l2 - 1] == dp[l1][l2]) c = str2[--l2];

ans.push_front(c);

}

return {begin(ans), end(ans)};

}

};

花花酱 LeetCode 718. Maximum Length of Repeated Subarray

By zxi on May 17, 2019

iven two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

Solution: DP

dp[i][j] := max length of (A[0:i], B[0:j])

dp[i][j] = dp[i – 1][j – 1] + 1 if A[i-1] == B[j-1] else 0

Time complexity: O(m*n)
Space complexity: O(m*n) -> O(n)

C++ S:O(mn)

// Author: Huahua, 176 ms / 106.4 MB

class Solution {

public:

int findLength(vector<int>& A, vector<int>& B) {

int m = A.size();

int n = B.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 (A[i - 1] == B[j - 1]) {

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

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

}

return ans;

}

};

C++ S:O(min(m,n))

// Author: Huahua, 152 ms / 9.1 MB

class Solution {

public:

int findLength(vector<int>& A, vector<int>& B) {

if (A.size() < B.size()) swap(A, B);

int m = A.size();

int n = B.size();

vector<int> dp(n + 1);

int ans = 0;

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

for (int j = n; j >= 1; --j) {

dp[j] = A[i - 1] == B[j - 1] ? dp[j - 1] + 1 : 0;

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

}

return ans;

}

};

花花酱 LeetCode 1043. Partition Array for Maximum Sum

By zxi on May 14, 2019

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]

Note:

1 <= K <= A.length <= 500
0 <= A[i] <= 10^6

Solution: DP

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

dp[i] := max sum of A[1] ~ A[i]
init: dp[0] = 0
transition: dp[i] = max{dp[i – k] + max(A[i-k:i]) * k}, 1 <= k <= min(i, K)
ans: dp[n]

A = | 2 | 1 | 4 | 3 |
K = 3
dp[0] = 0
dp[1] = max(dp[0] + 2 * 1) = 2
dp[2] = max(dp[0] + 2 * 2, dp[1] + 1 * 1) = max(4, 3) = 4
dp[3] = max(dp[0] + 4 * 3, dp[1] + 4 * 2, dp[2] + 4 * 1) = max(12, 10, 8) = 12
dp[4] = max(dp[1] + 4 * 3, dp[2] + 4 * 2, dp[3] + 3 * 1) = max(14, 12, 15) = 15
best = | 4 | 4 | 4 | 3 |

C++

class Solution {

public:

int maxSumAfterPartitioning(vector<int>& A, int K) {

int n = A.size();

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

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

int m = INT_MIN;

for (int k = 1; k <= K && i - k >= 0; ++k) {

m = max(m, A[i - k]);

dp[i] = max(dp[i], dp[i - k] + m * k);

}

return dp[n];

}

};

花花酱 LeetCode 279. Perfect Squares

By zxi on April 17, 2019

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Solution 1: DP

dp[i] := ans
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} 1 <= j * j <= i

dp[5] = min{
dp[5 – 2 * 2] + 1 = dp[1] + 1 = (dp[1 – 1 * 1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1 * 1] + 1 = dp[3] + 1 = (dp[3 – 1 * 1] + 1) + 1 = dp[1] + 2 = dp[1 – 1*1] + 1 + 2 = dp[0] + 3 = 3
};

dp[5] = 2

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

C++

// Author: Huahua, running time: 104 ms

class Solution {

public:

int numSquares(int n) {

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

dp[0] = 0;

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

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

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

return dp[n];

}

};

花花酱 LeetCode 1000. Minimum Cost to Merge Stones

By zxi on March 2, 2019

There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.

A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.

Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Example 1:

Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation: 
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.

Example 2:

Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.

Example 3:

Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation: 
We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.

Note:

1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

Solution: DP

dp[i][j][k] := min cost to merge subarray i ~ j into k piles
Init: dp[i][j][k] = 0 if i==j and k == 1 else inf
ans: dp[0][n-1][1]
transition:
1. dp[i][j][k] = min{dp[i][m][1] + dp[m+1][j][k-1]} for all i <= m < j
2. dp[i][j][1] = dp[i][j][K] + sum(A[i]~A[j])

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

C++

// Running time: 12 ms, 12.1 MB

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

const int kInf = 1e9;

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stones[i];

// dp[i][j][k] := min cost to merge subarray i~j into k piles.

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

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

dp[i][i][1] = 0;

for (int l = 2; l <= n; ++l) // subproblem length

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

int j = i + l - 1; // end

for (int k = 2; k <= K; ++k) // piles

for (int m = i; m < j; m += K - 1) // split point

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

dp[i][j][1] = dp[i][j][K] + sums[j + 1] - sums[i];

}

return dp[0][n - 1][1];

}

};

C++/top down

// Author: Huahua, running time: 12 ms

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

const int kInf = 1e9;

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stones[i];

vector<vector<vector<int>>> cache(n, vector<vector<int>>(n, vector<int>(K + 1, INT_MAX)));

std::function<int(int, int, int)> dp = [&stones, &sums, &cache, kInf, n, K, &dp](int i, int j, int k) {

if ((j - i + 1 - k) % (K - 1)) return kInf;

if (i == j) return k == 1 ? 0 : kInf;

if (cache[i][j][k] != INT_MAX) return cache[i][j][k];

if (k == 1)

return cache[i][j][k] = dp(i, j, K) + sums[j + 1] - sums[i];

int ans = kInf;

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

int l = dp(i, m, 1);

if (l >= ans) continue;

int r = dp(m + 1, j, k - 1);

if (r >= ans) continue;

ans = min(ans, l + r);

}

return cache[i][j][k] = ans;

};

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

}

};

Solution 2: DP

dp[l][i] := min cost to merge [i, i + l) into as less piles as possible. Number of merges will be (l-1) / (K – 1) and
Transition: dp[l][i] = min(dp[m][i] + dp[l – m][i + m]) for 1 <= m < l
if ((l – 1) % (K – 1) == 0) [i, i + l) can be merged into 1 pile, dp[l][i] += sum(A[i:i+l])

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

C++

// Author: Huahua 4ms, 9.6 MB

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stones[i];

const int kInf = 1e9;

// dp[i][j] := min cost to merge subarray A[i] ~ A[j] into (j-i)%(K-1) + 1 piles

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

for (int i = 0; i < n; ++i) dp[i][i] = 0;

for (int l = 2; l <= n; ++l) // subproblem length

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

int j = i + l - 1;

for (int m = i; m < j ; m += K - 1) // split point

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

// If the current length can be merged into 1 pile

// The cost is independent of the merge orders.

if ((l - 1) % (K - 1) == 0)

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

}

return dp[0][n - 1];

}

};

C++/Top-Down

// Author: Huahua, 4 ms

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

const int kInf = 1e9;

vector<vector<int>> cache(n, vector<int>(n, kInf));

vector<int> sums(n + 1);

for (int i = 0; i < stones.size(); ++i) sums[i + 1] = sums[i] + stones[i];

std::function<int(int, int)> dp;

dp = [&stones, &sums, &cache, &dp, K, kInf](int i, int j) {

const int l = j - i + 1;

if (l < K) return 0;

if (cache[i][j] != kInf) return cache[i][j];

int ans = kInf;

for (int m = i; m < j ; m += K - 1) // split point

ans = min(ans, dp(i, m) + dp(m + 1, j));

if ((l - 1) % (K - 1) == 0)

ans += sums[j + 1] - sums[i];

return cache[i][j] = ans;

};

return dp(0, n - 1);

}

};

Posts published in “Dynamic Programming”

花花酱 LeetCode 1092. Shortest Common Supersequence

Solution: LCS

C++

花花酱 LeetCode 718. Maximum Length of Repeated Subarray

Solution: DP

C++ S:O(mn)

C++ S:O(min(m,n))

花花酱 LeetCode 1043. Partition Array for Maximum Sum

Solution: DP

C++

花花酱 LeetCode 279. Perfect Squares

Solution 1: DP

C++

花花酱 LeetCode 1000. Minimum Cost to Merge Stones

Solution: DP

C++

C++/top down

Solution 2: DP

C++

C++/Top-Down