Posts published in “Dynamic Programming”

花花酱LeetCode 983. Minimum Cost For Tickets

By zxi on January 27, 2019

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

a 1-day pass is sold for costs[0] dollars;
a 7-day pass is sold for costs[1] dollars;
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 for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

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.

Note:

1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

Solution: DP

dp[i] := min cost to cover the i-th day
dp[0] = 0
dp[i] = min(dp[i – 1] + costs[0], dp[i – 7] + costs[1], dp[i – 30] + costs[2])

C++

// Author: Huahua, running time: 0 ms

class Solution {

public:

int mincostTickets(vector<int>& days, vector<int>& costs) {

vector<int> req(days.back() + 1);

vector<int> dp(days.back() + 1);

for (int day : days) req[day] = 1;

dp[0] = 0;

for (int i = 1; i < dp.size(); ++i) {

if (!req[i]) {

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

continue;

}

dp[i] = dp[i - 1] + costs[0];

dp[i] = min(dp[i], dp[max(0, i - 7)] + costs[1]);

dp[i] = min(dp[i], dp[max(0, i - 30)] + costs[2]);

}

return dp.back();

}

};

Python

// Author: Huahua, running time: 60 ms

class Solution:

def mincostTickets(self, days: 'List[int]', costs: 'List[int]') -> 'int':

req = set(days)

dp = [0] * (days[-1] + 1)

for i in range(1, len(dp)):

if not i in req:

dp[i] = dp[i - 1]

continue

dp[i] = min(dp[max(0, i - 1)] + costs[0],

dp[max(0, i - 7)] + costs[1],

dp[max(0, i - 30)] + costs[2])

return dp[-1]

花花酱 LeetCode 85. Maximal Rectangle

By zxi on January 26, 2019

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Solution: DP

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

dp[i][j] := max length of all 1 sequence ends with col j, at the i-th row.
transition:
dp[i][j] = 0 if matrix[i][j] == ‘0’
= dp[i][j-1] + 1 if matrix[i][j] == ‘1’

C++

class Solution {

public:

int maximalRectangle(vector<vector<char> > &matrix) {

int r = matrix.size();

if (r == 0) return 0;

int c = matrix[0].size();

// dp[i][j] := max len of all 1s ends with col j at row i.

vector<vector<int>> dp(r, vector<int>(c));

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

for (int j = 0; j < c; ++j)

dp[i][j] = (matrix[i][j] == '1') ? (j == 0 ? 1 : dp[i][j - 1] + 1) : 0;

int ans = 0;

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

for (int j = 0; j < c; ++j) {

int len = INT_MAX;

for (int k = i; k < r; k++) {

len = min(len, dp[k][j]);

if (len == 0) break;

ans = max(len * (k - i + 1), ans);

}

return ans;

}

};

花花酱 LeetCode 978. Longest Turbulent Subarray

By zxi on January 20, 2019

A subarray A[i], A[i+1], ..., A[j] of A is said to be turbulent if and only if:

For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1]when k is odd.

That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size turbulent subarray of A.

Example 1:

Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])

Example 2:

Input: [4,8,12,16]
Output: 2

Example 3:

Input: [100]
Output: 1

Note:

1 <= A.length <= 40000
0 <= A[i] <= 10^9

Solution: DP

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

C++

// Author: Huahua, running time: 120 ms

class Solution {

public:

int maxTurbulenceSize(vector<int>& A) {

vector<int> up(A.size(), 1);

vector<int> down(A.size(), 1);

int ans = 1;

for (int i = 1; i < A.size(); ++i) {

if (A[i] > A[i - 1]) up[i] = down[i - 1] + 1;

if (A[i] < A[i - 1]) down[i] = up[i - 1] + 1;

ans = max(ans, max(up[i], down[i]));

}

return ans;

}

};

花花酱 LeetCode 974. Subarray Sums Divisible by K

By zxi on January 17, 2019

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5 
Output: 7 
Explanation: There are 7 subarrays with a sum divisible by K = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

Solution: Count prefix sums

let c[i] denotes the counts of prefix_sum % K init: c[0] = 1
Whenever we end up with the same prefix sum (after modulo), which means there are subarrys end with current element that is divisible by K (0 modulo).

e.g. A = [4,5,0,-2,-3,1], K = 5
[4,5] has prefix sum of 4, which happens at index 0 [4], and index 1, [4,5]
[4,5,0] also has a prefix sum of 4, which means [4, {5,0}], [4,5, {0}] are divisible by K.

ans += (c[prefix_sum] – 1)
i = 0, prefix_sum = 0, c[(0+4)%5] = c[4] = 1, ans = 0
i = 1, prefix_sum = 4+5, c[(4+5)%5] = c[4] = 2, ans = 0+2-1=0 => [5]
i = 2, prefix_sum = 4+0, c[(4+0)%5] = c[4] = 3, ans = 1+3-1=3 => [5], [5,0], [0]
i = 3, prefix_sum = 4-2, c[(4-2)%5] = c[2] = 1, ans = 3
i = 4, prefix_sum = 2-3, c[(2-3+5)%5] = c[4] = 4, ans = 3+4-1=6 => [5],[5,0],[0],[5,0,-2,-3], [0,-2,-3],[-2,-3]
i = 5, prefix_sum = 4+1, c[(4+1)%5] = c[0] = 2, ans = 6 + 2 – 1 =>
[5],[5,0],[0],[5,0,-2,-3], [0,-2,-3],[-2,-3], [4,5,0,-2,-3,1]

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

C++

class Solution {

public:

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

vector<int> c(K);

c[0] = 1;

int ans = 0;

int sum = 0;

for (int a : A) {

sum = (sum + a % K + K) % K;

ans += c[sum]++;

}

return ans;

}

};

Python3

class Solution:

def subarraysDivByK(self, A, K):

c = [0] * K

c[0] = 1

s = 0

ans = 0

for a in A:

s = (s + a % K + K) % K

ans += c[s]

c[s] += 1

return ans

花花酱 LeetCode 975. Odd Even Jump

By zxi on January 15, 2019

You are given an integer array A. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, …) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, …) jumps in the series are called even numbered jumps.

You may from index i jump forward to index j (with i < j) in the following way:

During odd numbered jumps (ie. jumps 1, 3, 5, …), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
During even numbered jumps (ie. jumps 2, 4, 6, …), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
(It may be the case that for some index i, there are no legal jumps.)

A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)

Return the number of good starting indexes.

Example 1:

Input: [10,13,12,14,15] 
Output: 2

Example 2:

Input: [2,3,1,1,4] 
Output: 3

Example 3:

Input: [5,1,3,4,2] 
Output: 3

Note:

1 <= A.length <= 20000
0 <= A[i] < 100000

Solution: Binary Search + DP

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

C++

class Solution {

public:

int oddEvenJumps(vector<int>& A) {

const int n = A.size();

map<int, int> m;

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

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

m[A[n - 1]] = n - 1;

int ans = 1;

for (int i = n - 2; i >= 0; --i) {

auto o = m.lower_bound(A[i]);

if (o != m.end()) dp[i][0] = dp[o->second][1];

auto e = m.upper_bound(A[i]);

if (e != m.begin()) dp[i][1] = dp[prev(e)->second][0];

if (dp[i][0]) ++ans;

m[A[i]] = i;

}

return ans;

}

};