Posts tagged as “dp”

花花酱 LeetCode 416. Partition Equal Subset Sum

By zxi on December 31, 2017

题目大意：

给你一个正整数的数组，问你能否把元素划分成元素和相等的两组。

Problem:

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Idea:

DP 动态规划

Solution:

Time complexity: O(n*sum)

Space complexity: O(sum)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

bool canPartition(vector<int>& nums) {

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum % 2 != 0) return false;

vector<int> dp(sum + 1, 0);

dp[0] = 1;

for (const int num : nums) {

for (int i = sum; i >= 0; --i)

if (dp[i]) dp[i + num] = 1;

if (dp[sum / 2]) return true;

}

return false;

}

};

花花酱 LeetCode 746. Min Cost Climbing Stairs

By zxi on December 17, 2017

Problem:

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

Input: cost = [10, 15, 20]

Output: 15

Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

Output: 6

Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].

题目大意:

有一个楼梯，要离开i层需要付cost[i]的费用，每次可以爬1层或2层。问你最少花多少钱能够达到顶楼。

Solution:

C++ / Recursion + Memorization 记忆化递归

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

vector<int> m(cost.size() + 1);

return dp(cost, m, cost.size());

}

private:

// min cost to climb to i-th step

int dp(vector<int>& cost, vector<int>& m, int i) {

if (i <= 1) return 0;

if (m[i] > 0) return m[i];

return m[i] = min(dp(cost, m, i - 1) + cost[i - 1],

dp(cost, m, i - 2) + cost[i - 2]);

}

};

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

vector<int> m(cost.size() + 1);

return min(dp(cost, m, cost.size() - 1),

dp(cost, m, cost.size() - 2));

}

private:

// min cost before leaving i-th step

int dp(vector<int>& cost, vector<int>& m, int i) {

if (i < 0) return 0;

if (m[i] > 0) return m[i];

return m[i] = min(dp(cost, m, i - 1), dp(cost, m, i - 2)) + cost[i];

}

};

C++ / DP 动态规划

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

const int n = cost.size();

vector<int> dp(n, INT_MAX); // d[i] min cost before leaving i

dp[0] = cost[0];

dp[1] = cost[1];

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

dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

// We can reach top from either n - 1, or n - 2

return min(dp[n - 1], dp[n - 2]);

}

};

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

// dp[i] : min cost to climb to n-th step

vector<int> dp(cost.size() + 1, 0);

for (int i = 2; i <= cost.size(); ++i)

dp[i] = min(dp[i - 1] + cost[i - 1],

dp[i - 2] + cost[i - 2]);

return dp[cost.size()];

}

};

O(1) Space

// Author: Huahua

// Runtime: 15 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

int dp1 = 0;

int dp2 = 0;

for (int i = 2; i <= cost.size(); ++i) {

int dp = min(dp1 + cost[i - 1], dp2 + cost[i - 2]);

dp2 = dp1;

dp1 = dp;

}

return dp1;

}

};

花花酱 LeetCode 377. Combination Sum IV

By zxi on December 15, 2017

Problem:

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]

target = 4

The possible combination ways are:

(1, 1, 1, 1)

(1, 1, 2)

(1, 2, 1)

(1, 3)

(2, 1, 1)

(2, 2)

(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

题目大意：给你一些数和一个目标值，问使用这些数(每个数可以被使用任意次数)加起来等于目标值的组合（其实是不重复的排列）有多少种。

Idea:

Solution:

C++ / Recursion + Memorization

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

int combinationSum4(vector<int>& nums, int target) {

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

m_[0] = 1;

return dp(nums, target);

}

private:

int dp(const vector<int>& nums, int target) {

if (target < 0) return 0;

if (m_[target] != -1) return m_[target];

int ans = 0;

for (const int num : nums)

ans += dp(nums, target - num);

return m_[target] = ans;

}

vector<int> m_;

};

C++ / DP

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

int combinationSum4(vector<int>& nums, int target) {

vector<int> dp(target + 1, 0); // dp[i] # of combinations sum up to i

dp[0] = 1;

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

for (const int num : nums)

if (i - num >= 0)

dp[i] += dp[i - num];

return dp[target];

}

};

Related Problems:

花花酱 LeetCode 740. Delete and Earn

By zxi on December 5, 2017

Problem:

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete everyelement equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Input: nums = [3, 4, 2]

Output: 6

Explanation:

Delete 4 to earn 4 points, consequently 3 is also deleted.

Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]

Output: 9

Explanation:

Delete 3 to earn 3 points, deleting both 2's and the 4.

Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.

9 total points are earned.

Note:

The length of nums is at most 20000.
Each element nums[i] is an integer in the range [1, 10000].

Idea:

Reduce the problem to House Robber Problem

Key observations: If we take nums[i]

We can safely take all of its copies.
We can’t take any of copies of nums[i – 1] and nums[i + 1]

This problem is reduced to 198 House Robber.

Houses[i] has all the copies of num whose value is i.

[3 4 2] -> [0 2 3 4], rob([0 2 3 4]) = 6

[2, 2, 3, 3, 3, 4] -> [0 2*2 3*3 4], rob([0 2*2 3*3 4]) = 9

Time complexity: O(n+r) reduction + O(r) solving rob = O(n + r)

Space complexity: O(r)

r = max(nums) – min(nums) + 1

Time complexity: O(n + r)

Space complexity: O(r)

Solution:

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int deleteAndEarn(vector<int>& nums) {

if (nums.empty()) return 0;

const auto range = minmax_element(nums.begin(), nums.end());

const int l = *(range.first);

const int r = *(range.second);

vector<int> points(r - l + 1, 0);

for (const int num : nums)

points[num - l] += num;

return rob(points);

}

private:

// From LeetCode 198. House Robber

int rob(const vector<int>& nums) {

int dp2 = 0;

int dp1 = 0;

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

int dp = max(dp2 + nums[i], dp1);

dp2 = dp1;

dp1 = dp;

}

return dp1;

}

};

Related Problem:

花花酱 LeetCode 198. House Robber

花花酱 LeetCode 198. House Robber

By zxi on December 5, 2017

Problem:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Idea:

Time complexity: O(n)

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

Solution:

C++ / Recursion + Memorization

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

int rob(vector<int>& nums) {

const int n = nums.size();

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

return rob(nums, n - 1);

}

private:

int rob(const vector<int>& nums, int i) {

if (i < 0) return 0;

if (m_[i] >= 0) return m_[i];

return m_[i] = max(rob(nums, i - 2) + nums[i],

rob(nums, i - 1));

}

vector<int> m_;

};

C++ / DP

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

int rob(vector<int>& nums) {

if (nums.empty()) return 0;

vector<int> dp(nums.size(), 0);

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

dp[i] = max((i > 1 ? dp[i - 2] : 0) + nums[i],

(i > 0 ? dp[i - 1] : 0));

return dp.back();

}

};

C++ / O(1) Space

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

int rob(vector<int>& nums) {

if (nums.empty()) return 0;

int dp2 = 0;

int dp1 = 0;

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

int dp = max(dp2 + nums[i], dp1);

dp2 = dp1;

dp1 = dp;

}

return dp1;

}

};