Posts published in “Dynamic Programming”

花花酱 LeetCode 1269. Number of Ways to Stay in the Same Place After Some Steps

By zxi on November 24, 2019

You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.

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

Example 1:

Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

Example 2:

Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

Example 3:

Input: steps = 4, arrLen = 2
Output: 8

Constraints:

1 <= steps <= 500
1 <= arrLen <= 10^6

Solution: DP

Since we can move at most steps, we can reduce the arrLen to min(arrLen, steps + 1).

dp[i][j] = dp[i-1][j – 1] + dp[i-1][j] + dp[i-1][j+1] // sum of right, stay, left

Time complexity: O(steps * steps)
Space complexity: O(steps)

C++

// Author: Huahua

class Solution {

public:

int numWays(int steps, int arrLen) {

const int kMod = 1e9 + 7;

arrLen = min(steps + 1, arrLen);

vector<int> dp(arrLen);

dp[0] = 1;

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

vector<int> tmp(dp.size());

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

tmp[j] = dp[j];

if (j > 0) tmp[j] = (tmp[j] + dp[j - 1]) % kMod;

if (j < arrLen - 1) tmp[j] = (tmp[j] + dp[j + 1]) % kMod;

}

swap(dp, tmp);

}

return dp[0];

}

};

花花酱 LeetCode 1238. Circular Permutation in Binary Representation

By zxi on October 27, 2019

Given 2 integers n and start. Your task is return any permutation p of (0,1,2.....,2^n -1) such that :

p[0] = start
p[i] and p[i+1] differ by only one bit in their binary representation.
p[0] and p[2^n -1] must also differ by only one bit in their binary representation.

Example 1:

Input: n = 2, start = 3
Output: [3,2,0,1]
Explanation: The binary representation of the permutation is (11,10,00,01). 
All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]

Example 2:

Input: n = 3, start = 2
Output: [2,6,7,5,4,0,1,3]
Explanation: The binary representation of the permutation is (010,110,111,101,100,000,001,011).

Constraints:

1 <= n <= 16
0 <= start < 2 ^ n

Solution 1: Gray Code (DP) + Rotation

Gray code starts with 0, need to rotate after generating the list.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> circularPermutation(int n, int start) {

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

dp[0] = {0};

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

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

for (int j = dp[i - 1].size() - 1; j >= 0; --j)

dp[i].push_back(dp[i - 1][j] | (1 << (i - 1)));

}

for (auto it = begin(dp[n]); it != end(dp[n]); ++it)

if (*it == start) {

rotate(begin(dp[n]), it, end(dp[n]));

break;

}

return dp[n];

}

};

Solution 2: Gray code with a start

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

C++

// Author: Huahua

class Solution {

public:

vector<int> circularPermutation(int n, int start) {

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

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

ans[i] = start ^ i ^ i >> 1;

return ans;

}

};

花花酱 LeetCode 1240. Tiling a Rectangle with the Fewest Squares

By zxi on October 27, 2019

Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.

Example 1:

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)

Example 2:

Input: n = 5, m = 8
Output: 5

Example 3:

Input: n = 11, m = 13
Output: 6

Solution1: DP + Cheating

DP can not handle case 3, for m, n <= 13, (11,13) is the only case of that special case.

dp[i][j] := min squares to tile a i x j rectangle.

dp[i][i] = 1

dp[i][j] = min(dp[r][j] + dp[i-r][j], dp[i][c] + dp[i][j – c]), 1 <= r <= i/2, 1 <= c <= j /2

answer dp[m][n]

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

C++

// Author: Huahua

class Solution {

public:

int tilingRectangle(int n, int m) {

if (max(n, m) == 13 && min(n, m) == 11) return 6;

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] = INT_MAX;

if (i == j) {

dp[i][j] = 1;

continue;

}

for (int r = 1; r <= i / 2; ++r)

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

for (int c = 1; c <= j / 2; ++c)

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

}

return dp[n][m];

}

};

Solution 2: DFS

C++

// Author: Huahua

class Solution {

public:

int tilingRectangle(int n, int m) {

if (n > m) return tilingRectangle(m, n);

int ans = n * m;

vector<int> h(n);

function<void(int)> dfs = [&](int cur) {

if (cur >= ans) return;

auto it = min_element(begin(h), end(h));

if (*it == m) { // All filled

ans = cur;

return;

}

int low = *it;

int s = it - begin(h);

int e = s;

// Find the base

while (e < n && h[e] == h[s] && (e - s + 1 + low) <= m) ++e;

for (int i = --e; i >= s; --i) {

// Try all possible square sizes in reverse order.

int size = i - s + 1;

for (int j = s; j <= i; ++j) h[j] += size;

dfs(cur + 1);

for (int j = s; j <= i; ++j) h[j] -= size;

}

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 1235. Maximum Profit in Job Scheduling

By zxi on October 24, 2019

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime , endTime and profit arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:


Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

Solution: DP + binary search

Sort jobs by ending time.
dp[t] := max profit by end time t.

for a job = (s, e, p)
dp[e] = dp[u] + p, u <= s, and if dp[u] + p > last_element in dp.

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

C++

// Author: Huahua

class Solution {

public:

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {

const int n = startTime.size();

vector<vector<int>> jobs(n);

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

jobs[i] = {endTime[i], startTime[i], profit[i]};

sort(begin(jobs), end(jobs));

int ans = 0;

map<int, int> m{{0, 0}}; // {end_time -> max_profit}

for (const auto& job : jobs) {

int p = prev(m.upper_bound(job[1]))->second + job[2];

if (p > rbegin(m)->second) {

m[job[0]] = p;

}

return rbegin(m)->second;

}

};

花花酱 LeetCode 1230. Toss Strange Coins

By zxi on October 19, 2019

You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed.

Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.

Example 1:

Input: prob = [0.4], target = 1
Output: 0.40000

Example 2:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

Constraints:

1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
Answers will be accepted as correct if they are within 10^-5 of the correct answer.

Solution: DP

dp[i][j] := prob of j coins face up after tossing first i coins.
dp[i][j] = dp[i-1][j] * (1 – p[i]) + dp[i-1][j-1] * p[i]

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

C++

// Author: Huahua

class Solution {

public:

double probabilityOfHeads(vector<double>& prob, int target) {

const int n = prob.size();

vector<double> dp(target + 1);

dp[0] = 1.0;

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

for (int j = min(i + 1, target); j >= 0; --j)

dp[j] = dp[j] * (1 - prob[i]) + (j > 0 ? dp[j - 1] : 0) * prob[i];

return dp[target];

}

};

Solution 2: Recursion + Memorization

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

C++

// Author: Huahua

class Solution {

public:

double probabilityOfHeads(vector<double>& prob, int target) {

vector<vector<double>> mem(prob.size() + 1, vector<double>(target + 1, -1));

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

if (k > n || k < 0) return 0.0;

if (n == 0) return 1.0;

if (mem[n][k] >= 0) return mem[n][k];

const double p = prob[n - 1];

return mem[n][k] = p * dp(n - 1, k - 1) + (1 - p) * dp(n - 1, k);

};

return dp(prob.size(), target);

}

};