Press "Enter" to skip to content

Posts tagged as “dp”

花花酱 LeetCode Weekly Contest 137

1046. Last Stone Weight

Solution: Simulation (priority_queue)

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

C++

1047. Remove All Adjacent Duplicates In String

Solution: Stack / Deque

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

C++

1048. Longest String Chain

Solution: DP

dp[i] := max length of chain of (A[0] ~ A[i-1])

dp[i] = max{dp[j] + 1} if A[j] is prederrsor of A[i], 1 <= j <i

Time complexity: O(n^2*l)
Space complexity: O(n)

C++

1049. Last Stone Weight II

Solution: DP / target sum

Time complexity: O(n * S) = O(n * 100)

Space complexity: O(S) = O(100)

C++

花花酱 LeetCode 718. Maximum Length of Repeated Subarray

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. 1 <= len(A), len(B) <= 1000
  2. 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)

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

花花酱 LeetCode 1043. Partition Array for Maximum Sum

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. 1 <= K <= A.length <= 500
  2. 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++

花花酱 LeetCode Weekly Contest 133

LeetCode 1029 Two City Scheduling

Solution1: DP

dp[i][j] := min cost to put j people into city A for the first i people
dp[0][0] = 0
dp[i][0] = dp[i -1][0] + cost_b
dp[i][j] = min(dp[i – 1][j] + cost_b, dp[i – 1][j – 1] + cost_a)
ans := dp[n][n/2]

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

C++

Solution 2: Greedy

Sort by cost_a – cost_b

Choose the first n/2 people for A, rest for B

Time complexity: O(nlogn)
Space complexity: O(1)

C++

1030. Matrix Cells in Distance Order

Solution: Sorting

Time complexity: O(RC*log(RC))
Space complexity: O(RC)

C++

1031. Maximum Sum of Two Non-Overlapping Subarrays

Solution: Prefix sum

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

C++

1032. Stream of Characters

Solution: Trie

Time complexity:

  • build O(sum(len(w))
  • query O(max(len(w))

Space complexity: O(sum(len(w))

C++

Java

花花酱 LeetCode 279. Perfect Squares

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++