Posts tagged as “dp”

花花酱 LeetCode 221. Maximal Square

By zxi on September 18, 2017

Problem:

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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Idea:

Dynamic programming

Solution 0: O(n^5)

Solution 1: O(n^3)

Solution 2: O(n^2)

Solution 1:

// Author: Huahua

// Time complexity: O(n^3)

// Running time: 39 ms

class Solution {

public:

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

if (matrix.empty()) return 0;

int m = matrix.size();

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

// sums[i][j] = sum(matrix[0][0] ~ matrix[i-1][j-1])

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

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

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

sums[i][j] = matrix[i - 1][j - 1] - '0'

+ sums[i - 1][j]

+ sums[i][j - 1]

- sums[i - 1][j - 1];

int ans = 0;

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

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

for (int k = min(m - i + 1, n - j + 1); k > 0; --k) {

int sum = sums[i + k - 1][j + k - 1]

- sums[i + k - 1][j - 1]

- sums[i - 1][j + k - 1]

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

// full of 1

if (sum == k*k) {

ans = max(ans, sum);

break;

}

return ans;

}

};

Solution 2:

// Author: Huahua

// Time complexity: O(n^2)

// Running time: 6 ms

class Solution {

public:

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

if (matrix.empty()) return 0;

int m = matrix.size();

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

vector<vector<int>> sizes(m, vector<int>(n, 0));

int ans = 0;

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

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

sizes[i][j] = matrix[i][j] - '0';

if (!sizes[i][j]) continue;

if (i == 0 || j == 0) {

// do nothing

} else if (i == 0)

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

else if (j == 0)

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

else

sizes[i][j] = min(min(sizes[i - 1][j - 1],

sizes[i - 1][j]),

sizes[i][j - 1]) + 1;

ans = max(ans, sizes[i][j]*sizes[i][j]);

}

return ans;

}

};

花花酱 LeetCode 673. Number of Longest Increasing Subsequence

By zxi on September 15, 2017

https://leetcode.com/problems/number-of-longest-increasing-subsequence

Problem:

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]

Output: 2

Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]

Output: 5

Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Idea:

Dynamic programming

Solution1:

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

int findNumberOfLIS(vector<int>& nums) {

int n = nums.size();

if (n == 0) return 0;

c_ = vector<int>(n, 0);

l_ = vector<int>(n, 0);

// Find the length LIS.

int max_len = 0;

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

max_len = max(max_len, len(nums, i));

// Checking all endings.

int ans = 0;

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

if (len(nums, i) == max_len)

ans += count(nums, i);

return ans;

}

private:

vector<int> c_; // c[i]: number of LIS ends with nums[i] / NLIS'

vector<int> l_; // l[i]: lengeh of LIS ends with nums[i] / LIS'

// Number of LIS ends with nums[n]

int count(const vector<int>& nums, int n) {

if (n == 0) return 1;

if (c_[n] > 0) return c_[n];

int total_count = 0;

int l = len(nums, n);

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

if (nums[n] > nums[i] && len(nums, i) == l-1)

total_count += count(nums, i);

if (total_count == 0)

total_count = 1;

return c_[n] = total_count;

}

// Length of LIS ends with nums[n]

int len(const vector<int>& nums, int n) {

if (n == 0) return 1;

if (l_[n] > 0) return l_[n];

int max_len = 1;

// Check every subarray

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

if (nums[n] > nums[i])

max_len = max(max_len, len(nums, i) + 1);

return l_[n] = max_len;

}

};

Solution2:

// Author: Huahua

// Running time: 33 ms

class Solution {

public:

int findNumberOfLIS(vector<int>& nums) {

int n = nums.size();

if (n == 0) return 0;

vector<int> c(n, 1);

vector<int> l(n, 1);

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

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

if (nums[i] > nums[j]) {

if (l[j] + 1 > l[i]) {

l[i] = l[j] + 1;

c[i] = c[j];

} else if (l[j] + 1 == l[i]) {

c[i] += c[j];

}

int max_len = *max_element(l.begin(), l.end());

int ans = 0;

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

if (l[i] == max_len)

ans += c[i];

return ans;

}

};

Related Problems:

花花酱 LeetCode 300. Longest Increasing Subsequence

By zxi on September 10, 2017

Problem:

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Idea:

Dynamic Programming

Time Complexity:

O(n^2)

Solution 1:

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

if (nums.empty()) return 0;

int n = nums.size();

auto f = vector<int>(n, 1);

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

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

if (nums[i] > nums[j])

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

return *max_element(f.begin(), f.end());

}

};

Solution 2: DP + Binary Search / Patience Sort

dp[i] := smallest tailing number of a increasing subsequence of length i + 1.

dp is an increasing array, we can use binary search to find the index to insert/update the array.

ans = len(dp)

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

C++

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

const int n = nums.size();

if (n == 0) return 0;

vector<int> dp;

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

auto it = lower_bound(begin(dp), end(dp), nums[i]);

if (it == end(dp))

dp.push_back(nums[i]);

else

*it = nums[i];

}

return dp.size();

}

};

Python3

class Solution:

def lengthOfLIS(self, nums: List[int]) -> int:

d = []

for x in nums:

i = bisect_left(d, x)

if i == len(d):

d.append(x)

else:

d[i] = x

return len(d)

Related Problems:

花花酱 LeetCode 62. Unique Paths

By zxi on September 9, 2017

Problem:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Idea:

Dynamic Programming

Solution1:

C++

// Author: Huahua

class Solution {

public:

int uniquePaths(int m, int n) {

if (m < 0 || n < 0) return 0;

if (m == 1 && n == 1) return 1;

if (f_[m][n] > 0) return f_[m][n];

int left_paths = uniquePaths(m - 1, n);

int top_paths = uniquePaths(m, n - 1);

f_[m][n] = left_paths + top_paths;

return f_[m][n];

}

private:

unordered_map<int, unordered_map<int, int>> f_;

};

Java

// Author: Huahua

// Running time: 0 ms

class Solution {

private int[][] dp;

private int m;

private int n;

public int uniquePaths(int m, int n) {

this.dp = new int[m][n];

this.m = m;

this.n = n;

return dfs(0, 0);

}

private int dfs(int x, int y) {

if (x > m - 1 || y > n - 1)

return 0;

if (x == m - 1 && y == n - 1)

return 1;

if (dp[x][y] == 0)

dp[x][y] = dfs(x + 1, y) + dfs(x , y + 1);

return dp[x][y];

}

Solution2:

// Author: Huahua

class Solution {

public:

int uniquePaths(int m, int n) {

auto f = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));

f[1][1] = 1;

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

for(int x = 1; x <= m; ++x) {

if (x == 1 && y == 1) {

continue;

} else {

f[y][x] = f[y-1][x] + f[y][x-1];

}

return f[n][m];

}

};

花花酱 LeetCode 128. Longest Consecutive Sequence

By zxi on March 15, 2017

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

class Solution {

public:

int longestConsecutive(vector<int> &num) {

unordered_map<int,int> m;

int ans = 0;

for(auto n : num) {

if(m.count(n)) continue;

if(m.count(n-1) && m.count(n+1)){

int l = m[n-1], r = m[n+1];

m[n] = m[n-l] = m[n+r] = r+l+1;

} else if(m.count(n-1)) {

int l = m[n-1];

m[n] = m[n-l] = l+1;

} else if(m.count(n+1)) {

int r = m[n+1];

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

} else {

m[n] = 1;

}

ans = max(ans, m[n]);

}

return ans;

}

};