Posts tagged as “dp”

花花酱 LeetCode 516. Longest Palindromic Subsequence

By zxi on May 28, 2018

Problem

题目大意：找出最长回文子序列的长度。

https://leetcode.com/problems/longest-palindromic-subsequence/description/

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"

Output:

One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:

"cbbd"

Output:

One possible longest palindromic subsequence is “bb”.

Solution: DP

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 102 ms

class Solution {

public:

int longestPalindromeSubseq(string s) {

const int n = s.length();

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

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

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

int j = i + l - 1;

if (i == j) {

dp[i][j] = 1;

continue;

}

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

if (s[i] == s[j])

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

}

return dp[0][n - 1];

}

};

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

int longestPalindromeSubseq(string s) {

const int n = s.length();

vector<int> dp0(n); // sols of len = l

vector<int> dp1(n); // sols of len = l - 1

vector<int> dp2(n); // sols of len = l - 2

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

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

int j = i + l - 1;

if (i == j) {

dp0[i] = 1;

continue;

}

if (s[i] == s[j])

dp0[i] = dp2[i + 1] + 2;

else

dp0[i] = max(dp1[i + 1], dp1[i]);

}

dp0.swap(dp1);

dp2.swap(dp0);

}

return dp1[0];

}

};

Python3

"""

Author: Huahua

Running time: 1276 ms

"""

class Solution:

def longestPalindromeSubseq(self, s):

n = len(s)

dp0 = [0] * n

dp1 = [1] * n

dp2 = [0] * n

for l in range(2, n + 1):

for i in range(0, n - l + 1):

j = i + l - 1

if s[i] == s[j]:

dp0[i] = dp2[i + 1] + 2

else:

dp0[i] = max(dp1[i + 1], dp1[i])

dp0, dp1, dp2 = dp2, dp0, dp1

return dp1[0]

// Author: Huahua

// Running time: 116 ms (beats 100%)

public class Solution {

public int LongestPalindromeSubseq(string s) {

var n = s.Length;

var dp0 = new int[n];

var dp1 = new int[n];

var dp2 = new int[n];

for (var l = 1; l <= n; ++l) {

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

int j = i + l - 1;

if (i == j) {

dp0[i] = 1;

continue;

}

if (s[i] == s[j])

dp0[i] = dp2[i + 1] + 2;

else

dp0[i] = Math.Max(dp1[i], dp1[i + 1]);

}

var tmp = dp2;

dp2 = dp1;

dp1 = dp0;

dp0 = tmp;

}

return dp1[0];

}

花花酱 LeetCode 329. Longest Increasing Path in a Matrix

By zxi on May 24, 2018

Problem

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution1: DFS + Memorization

Time complexity: O(mn)

Space complexity: O(mn)

C++

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int longestIncreasingPath(vector<vector<int>>& matrix) {

if (matrix.empty()) return 0;

m_ = matrix.size();

n_ = matrix[0].size();

dp_ = vector<vector<int>>(m_, vector<int>(n_, -1));

int ans = 0;

for (int y = 0; y < m_; ++y)

for (int x = 0; x < n_; ++x)

ans = max(ans, dfs(matrix, x, y));

return ans;

}

private:

int dfs(const vector<vector<int>>& mat, int x, int y) {

if (dp_[y][x] != -1) return dp_[y][x];

static int dirs[] = {0, -1, 0, 1, 0};

dp_[y][x] = 1;

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

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || ty < 0 || tx >= n_ || ty >= m_ || mat[ty][tx] <= mat[y][x])

continue;

dp_[y][x] = max(dp_[y][x], 1 + dfs(mat, tx, ty));

}

return dp_[y][x];

}

int m_;

int n_;

// dp[i][j]: max length start from (j, i)

vector<vector<int>> dp_;

};

Solution2: DP

Time complexity: O(mn*log(mn))

Space complexity: O(mn)

// Author: Huahua

// Running time: 63 ms

class Solution {

public:

int longestIncreasingPath(vector<vector<int>>& matrix) {

if (matrix.empty()) return 0;

int m = matrix.size();

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

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

int ans = 0;

vector<pair<int, pair<int, int>>> cells;

for (int y = 0; y < m; ++y)

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

cells.push_back({matrix[y][x], {x, y}});

sort(cells.rbegin(), cells.rend());

vector<int> dirs {0, 1, 0, -1, 0};

for (const auto& cell : cells) {

int x = cell.second.first;

int y = cell.second.second;

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

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;

if (matrix[ty][tx] <= matrix[y][x]) continue;

dp[y][x] = max(dp[y][x], 1 + dp[ty][tx]);

}

ans = max(ans, dp[y][x]);

}

return ans;

}

};

花花酱 LeetCode 826. Most Profit Assigning Work

By zxi on April 29, 2018

Problem

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job.

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, his profit is $0.

What is the most profit we can make?

Example 1:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100 
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.

Notes:

1 <= difficulty.length = profit.length <= 10000
1 <= worker.length <= 10000
difficulty[i], profit[i], worker[i] are in range [1, 10^5]

Solution 1: Sorting + Two pointers

Time complexity: O(nlogn + mlogm)

Space complexity: O(n)

// Author: Huahua

// Running time: 90 ms

class Solution {

public:

int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

const int n = difficulty.size();

vector<pair<int, int>> jobs; // difficulty, profit

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

jobs.emplace_back(difficulty[i], profit[i]);

std::sort(jobs.begin(), jobs.end());

std::sort(worker.begin(), worker.end());

int ans = 0;

int i = 0;

int best = 0;

for (int level : worker) {

while (i < n && level >= jobs[i].first)

best = max(best, jobs[i++].second);

ans += best;

}

return ans;

}

};

Solution 2: Bucket + Greedy

Key idea: for each difficulty D, find the most profit job whose requirement is <= D.

Three steps:

for each difficulty D, find the most profit job whose requirement is == D, best[D] = max{profit of difficulty D}.
if difficulty D – 1 can make more profit than difficulty D, best[D] = max(best[D], best[D – 1]).
The max profit each worker at skill level D can make is best[D].

Time complexity: O(n)

Space complexity: O(10000)

C++

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

const int N = 100000;

// max profit at difficulty i

vector<int> max_profit(N + 1, 0);

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

max_profit[difficulty[i]] = max(max_profit[difficulty[i]], profit[i]);

for (int i = 2; i <= N; ++i)

max_profit[i] = max(max_profit[i], max_profit[i - 1]);

int ans = 0;

for (int level : worker)

ans += max_profit[level];

return ans;

}

};

C++ using map

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

map<int, int> bests;

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

bests[difficulty[i]] = max(bests[difficulty[i]], profit[i]);

int best = 0;

for (auto it = bests.begin(); it != bests.end(); ++it)

it->second = best = max(it->second, best);

int ans = 0;

for (int level : worker)

ans += prev(bests.upper_bound(level))->second;

return ans;

}

};

花花酱 LeetCode 823. Binary Trees With Factors

By zxi on April 29, 2018

Problem

题目大意：给你一些可以重复使用的数字问能够构成多少种不同的特殊二叉树（根结点的值需为子节点值的乘积）。

https://leetcode.com/problems/binary-trees-with-factors/description/

Given an array of unique integers, each integer is strictly greater than 1.

We make a binary tree using these integers and each number may be used for any number of times.

Each non-leaf node’s value should be equal to the product of the values of it’s children.

How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.

Example 1:

Input: A = [2, 4]
Output: 3 Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

Note:

1 <= A.length <= 1000.
2 <= A[i] <= 10 ^ 9.

Solution: DP

Use dp[i] to denote the number of valid binary trees using the first i + 1 smallest elements and roots at A[i].

dp[i] = sum(dp[j] * dp[i/j]), 0 <= j < i, A[i] is a factor of A[j] and A[i] / A[j] also in A.

      A[i]
     /    \
 A[j]  (A[i]/A[j])
  / \     / \
 .....   .....

ans = sum(dp[i]), for all possible i.

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 53 ms

class Solution {

public:

int numFactoredBinaryTrees(vector<int>& A) {

constexpr long kMod = 1000000007;

std::sort(A.begin(), A.end());

unordered_map<int, long> dp;

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

dp[A[i]] = 1;

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

if (A[i] % A[j] == 0 && dp.count(A[i] / A[j]))

dp[A[i]] += (dp[A[j]] * dp[A[i] / A[j]]) % kMod;

}

long ans = 0;

for (const auto& kv : dp)

ans += kv.second;

return ans % kMod;

}

};

花花酱 LeetCode 818. Race Car

By zxi on April 15, 2018

Problem

题目大意：初始位置0速度+1，每次你可以加速（速度*2）或者倒车（速度变成-1*dir）。问最少需要执行多少步操作能够到达T。

https://leetcode.com/problems/race-car/description/

Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction “A”, your car does the following: position += speed, speed *= 2.

When you get an instruction “R”, your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. (Your position stays the same.)

For example, after commands “AAR”, your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

Example 1:
Input: 
target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.

Example 2:
Input: 
target = 6
Output: 5
Explanation: 
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6.

Note:

1 <= target <= 10000.

Visualization of the Solution

Solution 1: BFS

C++/Str

// Author: Huahua

// Running time: 221 ms

class Solution {

public:

int racecar(int target) {

queue<pair<int, int>> q;

q.push({0, 1});

unordered_set<string> v;

v.insert("0_1");

v.insert("0_-1");

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int pos = p.first;

int speed = p.second;

{

int pos1 = pos + speed;

int speed1 = speed * 2;

pair<int, int> p1{pos1, speed1};

if (pos1 == target) return steps + 1;

if (p1.first > 0 && p1.first < 2 * target)

q.push(p1);

}

{

int speed2 = speed > 0 ? -1 : 1;

pair<int, int> p2{pos, speed2};

string key2 = to_string(pos) + "_" + to_string(speed2);

if (!v.count(key2)) {

q.push(p2);

v.insert(key2);

}

++steps;

}

return -1;

}

};

C++/Int

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int racecar(int target) {

queue<pair<int, int>> q;

q.push({0, 1});

unordered_set<int> v;

v.insert({0, 2});

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int pos = p.first;

int speed = p.second;

pair<int, int> p1 = {pos + speed, speed * 2};

if (p1.first == target) return steps + 1;

if (p1.first > 0 && p1.first + speed < 2 * target)

q.push(p1);

int speed2 = speed > 0 ? -1 : 1;

pair<int, int> p2 = {pos, speed2};

int key = (pos << 2) | (speed2 + 1);

if (!v.count(key) && p2.first >= target / 2) {

q.push(p2);

v.insert(key);

}

++steps;

}

return -1;

}

};

Solution 2: DP O(TlogT)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int racecar(int target) {

m_ = vector<int>(target + 1, 0);

return dp(target);

}

private:

vector<int> m_;

int dp(int t) {

if (m_[t] > 0) return m_[t];

int n = ceil(log2(t + 1));

// AA...A (nA) best case

if (1 << n == t + 1) return m_[t] = n;

// AA...AR (nA + 1R) + dp(left)

m_[t] = n + 1 + dp((1 << n) - 1 - t);

for (int m = 0; m < n - 1; ++m) {

int cur = (1 << (n - 1)) - (1 << m);

//AA...ARA...AR (n-1A + 1R + mA + 1R) + dp(left)

m_[t] = min(m_[t], n + m + 1 + dp(t - cur));

}

return m_[t];

}

};

Solution 3: DP O(T^2)

m[t][d] : min steps to reach t and facing d (0 = right, 1 = left)

Time Complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 469 ms

constexpr int kMaxT = 10000;

int m[kMaxT + 1][2]={0};

class Solution {

public:

int racecar(int target) {

if (m[1][0] == 0) {

for (int t = 1; t <= kMaxT; ++t) {

const int n = ceil(log2(t + 1));

if (1 << n == t + 1) {

m[t][0] = n;

m[t][1] = n + 1;

continue;

}

const int l = (1 << n) - 1 - t;

m[t][0] = n + 1 + min(m[l][1], m[l][0] + 1);

m[t][1] = n + 1 + min(m[l][0], m[l][1] + 1);

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

const int mi = min(m[i][0] + 2, m[i][1] + 1);

m[t][0] = min(m[t][0], m[t - i][0] + mi);

m[t][1] = min(m[t][1], m[t - i][1] + mi);

}

return min(m[target][0], m[target][1]);

}

};

C++/opt

// Author: Huahua

// Running time: 361 ms

typedef unsigned char uint8;

constexpr int kMaxT = 10000;

uint8 m[kMaxT + 1][2]={0};

inline uint8 MIN(uint8 a, uint8 b) {

return a < b ? a : b;

}

class Solution {

public:

int racecar(int target) {

if (m[1][0] == 0) {

for (int t = 1; t <= kMaxT; ++t) {

const int n = ceil(log2(t + 1));

if (1 << n == t + 1) {

m[t][0] = n;

m[t][1] = n + 1;

continue;

}

const int l = (1 << n) - 1 - t;

m[t][0] = n + 1 + MIN(m[l][1], (uint8)(m[l][0] + 1));

m[t][1] = n + 1 + MIN(m[l][0], (uint8)(m[l][1] + 1));

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

const int mi = MIN(m[i][0] + 2, m[i][1] + 1);

m[t][0] = MIN(m[t][0], (uint8)(m[t - i][0] + mi));

m[t][1] = MIN(m[t][1], (uint8)(m[t - i][1] + mi));

}

return min(m[target][0], m[target][1]);

}

};

Java

// Author: Huahua

// Running time: 562 ms

class Solution {

private static int[][] m;

public int racecar(int target) {

if (m == null) {

final int kMaxT = 10000;

m = new int[kMaxT + 1][2];

for (int t = 1; t <= kMaxT; ++t) {

int n = (int)Math.ceil(Math.log(t + 1) / Math.log(2));

if (1 << n == t + 1) {

m[t][0] = n;

m[t][1] = n + 1;

continue;

}

int l = (1 << n) - 1 - t;

m[t][0] = n + 1 + Math.min(m[l][1], m[l][0] + 1);

m[t][1] = n + 1 + Math.min(m[l][0], m[l][1] + 1);

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

for (int d = 0; d <= 1; d++)

m[t][d] = Math.min(m[t][d], Math.min(

m[i][0] + 2 + m[t - i][d],

m[i][1] + 1 + m[t - i][d]));

}

return Math.min(m[target][0], m[target][1]);

}