Posts published in “Dynamic Programming”

花花酱 LeetCode 518. Coin Change 2

By zxi on March 2, 2018

题目大意：给你一些硬币的面值，问使用这些硬币（无限多块）能够组成amount的方法有多少种。

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note: You can assume that

0 <= amount <= 5000
1 <= coin <= 5000
the number of coins is less than 500
the answer is guaranteed to fit into signed 32-bit integer

Example 1:

Input: amount = 5, coins = [1, 2, 5]

Output: 4

Explanation: there are four ways to make up the amount:

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]

Output: 0

Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

1 2	Input: amount = 10, coins = [10] Output: 1

Idea: DP

Transition 1:

Let us use dp[i][j] to denote the number of ways to sum up to amount j using first i kind of coins.

dp[i][j] = dp[i – 1][j – coin] + dp[i – 1][j – 2* coin] + …

Time complexity: O(n*amount^2) TLE

Space complexity: O(n*amount) -> O(amount)

Transition 2:

Let us use dp[i] to denote the number of ways to sum up to amount i.

dp[i + coin] += dp[i]

Time complexity: O(n*amount)

Space complexity: O(amount)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int change(int amount, vector<int>& coins) {

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

dp[0] = 1;

for (const int coin : coins)

for (int i = 0; i <= amount - coin; ++i)

dp[i + coin] += dp[i];

return dp[amount];

}

};

Java

// Author: Huahua

// Running time: 7 ms

class Solution {

public int change(int amount, int[] coins) {

int[] dp = new int[amount + 1];

dp[0] = 1;

for (int coin : coins)

for (int i = 0; i <= amount - coin; ++i)

dp[i + coin] += dp[i];

return dp[amount];

}

Python

"""

Author: Huahua

Running time: 107 ms (beats 100%)

"""

class Solution(object):

def change(self, amount, coins):

dp = [1] + [0] * (amount);

for coin in coins:

for i in xrange(amount - coin + 1):

if dp[i]:

dp[i + coin] += dp[i]

return dp[amount]

Related Problems:

花花酱 LeetCode 322. Coin Change

花花酱 LeetCode 790. Domino and Tromino Tiling

By zxi on February 24, 2018

题目大意：有两种不同形状的骨牌(1×2长条形，L型）无限多块。给你一个2xN的板子，问一共有多少不同的方式可以完全覆盖。

We have two types of tiles: a 2×1 domino shape, and an “L” tromino shape. These shapes may be rotated.

XX <- domino

XX <- "L" tromino

Given N, how many ways are there to tile a 2 x N board? Return your answer modulo 10^9 + 7.

(In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.)

Example:

Input: 3

Output: 5

Explanation:

The five different ways are listed below, different letters indicates different tiles:

XYZ XXZ XYY XXY XYY

XYZ YYZ XZZ XYY XXY

Idea: DP

dp[i][0]: ways to cover i cols, both rows of i-th col are covered
dp[i][1]: ways to cover i cols, only top row of i-th col is covered
dp[i][2]: ways to cover i cols, only bottom row of i-th col is covered

Solution 1: DP

Time complexity: O(N)

Space complexity: O(N)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numTilings(int N) {

constexpr int kMod = 1000000007;

vector<vector<long>> dp(N + 1, vector<long>(3, 0));

dp[0][0] = dp[1][0] = 1;

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

dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2]) % kMod;

dp[i][1] = (dp[i - 2][0] + dp[i - 1][2]) % kMod;

dp[i][2] = (dp[i - 2][0] + dp[i - 1][1]) % kMod;

}

return dp[N][0];

}

};

C++ V2

Since dp[i][1] always equals to dp[i][2], we can simplify a bit.

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numTilings(int N) {

constexpr int kMod = 1000000007;

vector<vector<long>> dp(N + 1, vector<long>(2, 0));

dp[0][0] = dp[1][0] = 1;

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

dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + 2 * dp[i - 1][1]) % kMod;

dp[i][1] = (dp[i - 2][0] + dp[i - 1][1]) % kMod;

}

return dp[N][0];

}

};

Solution 2: DP

Another way to think about this problem

define: dp[i] ways to completely covert the i*2 board.

dp[0] = 1 # {}

dp[1] = 1 # {|}

dp[2] = 2 # {||, =}

dp[3] = 5 # {|||, |=, =|, ⌊⌉, ⌈⌋} = dp[2] ⊗ {|} + dp[1] ⊗ {=} + dp[0] ⊗ {⌊⌉, ⌈⌋}

dp[4] = 11 # dp[3] ⊗ {|} + dp[2] ⊗ {=} + dp[1] ⊗ {⌊⌉, ⌈⌋} + dp[0] ⊗ {⌊¯⌋,⌈_⌉}

dp[5] = 24 # dp[4] ⊗ {|} + dp[3] ⊗ {=} + 2*(dp[2] + dp[1] + dp[0])

...

dp[n] = dp[n-1] + dp[n-2] + 2*(dp[n-3] + ... + dp[0])

= dp[n-1] + dp[n-3] + [dp[n-2] + dp[n-3] + 2*(dp[n-4] + ... + dp[0])]

= dp[n-1] + dp[n-3] + dp[n-1]

= 2*dp[n-1] + dp[n-3]

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int numTilings(int N) {

constexpr int kMod = 1000000007;

vector<long> dp(N + 1, 1);

dp[2] = 2;

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

dp[i] = (dp[i - 3] + dp[i - 1] * 2) % kMod;

return dp[N];

}

};

花花酱 LeetCode 787. Cheapest Flights Within K Stops

By zxi on February 22, 2018

题目大意：给你一些城市之间的机票价格，问从src到dst的最少需要花多少钱，最多可以中转k个机场。

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example 1:

Input:

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]

src = 0, dst = 2, k = 1

Output: 200

Explanation:

The graph looks like this:

The cheapest price from city <code>0</code> to city <code>2</code> with at most 1 stop costs 200, as marked red in the picture.

Example 2:

Input:

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]

src = 0, dst = 2, k = 0

Output: 500

Explanation:

The graph looks like this:

The cheapest price from city <code>0</code> to city <code>2</code> with at most 0 stop costs 500, as marked blue in the picture.

Note:

The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.
The size of flights will be in range [0, n * (n - 1) / 2].
The format of each flight will be (src, dst, price).
The price of each flight will be in the range [1, 10000].
k is in the range of [0, n - 1].
There will not be any duplicated flights or self cycles.

Solution 1: DFS

w/o prunning TLE

w/ prunning Accepted

C++

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

g_.clear();

for (const auto& e : flights)

g_[e[0]].emplace_back(e[1], e[2]);

vector<int> visited(n, 0);

visited[src] = 1;

int ans = INT_MAX;

dfs(src, dst, K + 1, 0, visited, ans);

return ans == INT_MAX ? - 1 : ans;

}

private:

unordered_map<int, vector<pair<int,int>>> g_;

void dfs(int src, int dst, int k, int cost, vector<int>& visited, int& ans) {

if (src == dst) {

ans = cost;

return;

}

if (k == 0) return;

for (const auto& p : g_[src]) {

if (visited[p.first]) continue; // do not visit the same city twice.

if (cost + p.second > ans) continue; // IMPORTANT!!! prunning

visited[p.first] = 1;

dfs(p.first, dst, k - 1, cost + p.second, visited, ans);

visited[p.first] = 0;

}

};

Solution 2: BFS

C++

// Author: Huahua

// Running time: 20 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

unordered_map<int, vector<pair<int,int>>> g;

for (const auto& e : flights)

g[e[0]].emplace_back(e[1], e[2]);

int ans = INT_MAX;

queue<pair<int,int>> q;

q.push({src, 0});

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int curr = q.front().first;

int cost = q.front().second;

q.pop();

if (curr == dst)

ans = min(ans, cost);

for (const auto& p : g[curr]) {

if (cost + p.second > ans) continue; // Important: prunning

q.push({p.first, cost + p.second});

}

if (steps++ > K) break;

}

return ans == INT_MAX ? - 1 : ans;

}

};

Solution 3: Bellman-Ford algorithm

dp[k][i]: min cost from src to i taken up to k flights (k-1 stops)

init: dp[0:k+2][src] = 0

transition: dp[k][i] = min(dp[k-1][j] + price[j][i])

ans: dp[K+1][dst]

Time complexity: O(k * |flights|) / O(k*n^2)

Space complexity: O(k*n) -> O(n)

w/o space compression O(k*n)

C++ O(k*n)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

constexpr int kInfCost = 1e9;

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

dp[0][src] = 0;

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

dp[i][src] = 0;

for (const auto& p : flights)

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

}

return dp[K + 1][dst] >= kInfCost ? -1 : dp[K + 1][dst];

}

};

C++ O(n)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

constexpr int kInfCost = 1e9;

vector<int> cost(n, kInfCost);

cost[src] = 0;

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

vector<int> tmp(cost);

for (const auto& p : flights)

tmp[p[1]] = min(tmp[p[1]], cost[p[0]] + p[2]);

cost.swap(tmp);

}

return cost[dst] >= kInfCost ? -1 : cost[dst];

}

};

Java

// Author: Huahua

// Running time: 11 ms

class Solution {

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

final int kInfCost = 1<<30;

int[] cost = new int[n];

Arrays.fill(cost, kInfCost);

cost[src] = 0;

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

int[] tmp = cost.clone();

for(int[] p: flights)

tmp[p[1]] = Math.min(tmp[p[1]], cost[p[0]] + p[2]);

cost = tmp;

}

return cost[dst] >= kInfCost ? -1 : cost[dst];

}

Python3

"""

Author: Huahua

Running time: 132 ms

"""

class Solution:

def findCheapestPrice(self, n, flights, src, dst, K):

kInfCost = 1e9

cost = [kInfCost for _ in range(n)]

cost[src] = 0

for i in range(K + 1):

tmp = list(cost)

for p in flights:

tmp[p[1]] = min(tmp[p[1]], cost[p[0]] + p[2])

cost = tmp

return -1 if cost[dst] >= 1e9 else cost[dst]

花花酱 LeetCode 762. Prime Number of Set Bits in Binary Representation

By zxi on January 17, 2018

题目大意：求给定范围内，数的二进制形式中1的个数为素数个的数字的个数。

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: L = 6, R = 10

Output: 4

Explanation:

6 -> 110 (2 set bits, 2 is prime)

7 -> 111 (3 set bits, 3 is prime)

9 -> 1001 (2 set bits , 2 is prime)

10->1010 (2 set bits , 2 is prime)

Example 2:

Input: L = 10, R = 15

Output: 5

Explanation:

10 -> 1010 (2 set bits, 2 is prime)

11 -> 1011 (3 set bits, 3 is prime)

12 -> 1100 (2 set bits, 2 is prime)

13 -> 1101 (3 set bits, 3 is prime)

14 -> 1110 (3 set bits, 3 is prime)

15 -> 1111 (4 set bits, 4 is not prime)

Note:

L, R will be integers L <= R in the range [1, 10^6].
R - L will be at most 10000.

Solution 1: Brute Force

C++

// Author: Huahua

// Running time: 22 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

for (int n = L; n <= R; ++n)

if (isPrime(bits(n))) ++ans;

return ans;

}

private:

bool isPrime(int n) {

if (n <= 1) return false;

if (n == 2) return true;

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

if (n % i == 0) return false;

return true;

}

int bits(int n) {

int s = 0;

while (n) {

s += n & 1;

n >>= 1;

}

return s;

}

};

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};

for (int n = L; n <= R; ++n)

if (primes.count(__builtin_popcountll(n))) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 30 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

unordered_set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};

for (int n = L; n <= R; ++n)

if (primes.count(__builtin_popcountll(n))) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

vector<int> p(20, 0);

p[2] = p[3] = p[5] = p[7] = p[11] = p[13] = p[17] = p[19] = 1;

for (int n = L; n <= R; ++n)

if (p[__builtin_popcountll(n)]) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

constexpr int magic = 665772;

int ans = 0;

for (int n = L; n <= R; ++n)

if (magic & (1 << __builtin_popcountll(n))) ++ans;

return ans;

}

};

Java

// Author: Huahua

// Running time: 39 ms

class Solution {

public int countPrimeSetBits(int L, int R) {

int ans = 0;

for (int n = L; n <= R; ++n)

if (isPrime(bits(n))) ++ans;

return ans;

}

private boolean isPrime(int n) {

if (n <= 1) return false;

if (n == 2) return true;

for (int i = 2; i <= (int)Math.sqrt(n); ++i)

if (n % i == 0) return false;

return true;

}

private int bits(int n) {

int s = 0;

while (n != 0) {

s += n & 1;

n >>= 1;

}

return s;

}

Python2

"""

Author: Huahua

Running time: 1618 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def isPrime(n):

if n <= 1: return False

if n == 2: return True

for i in range(2, int(math.sqrt(n)) + 1):

if n % i == 0: return False

return True

def bits(n):

s = 0

while n != 0:

s += n & 1

n >>= 1

return s

ans = 0

for n in range(L, R + 1):

if isPrime(bits(n)): ans += 1

return ans

Python2

"""

Author: Huahua

Running time: 1163 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def bits(n):

s = 0

while n != 0:

s += n & 1

n >>= 1

return s

primes = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31])

ans = 0

for n in range(L, R + 1):

if bits(n) in primes: ans += 1

return ans

"""

Author: Huahua

Running time: 667 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def bits(n):

s = 0

while n != 0:

n &= n - 1;

s += 1

return s

ans = 0

while L <= R:

if (665772 >> bits(L)) & 1 > 0: ans += 1

L += 1

return ans

花花酱 LeetCode 494. Target Sum

By zxi on January 9, 2018

题目大意：给你一串数字，你可以在每个数字前放置+或-，问有多少种方法可以使得表达式的值等于target。You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.

Output: 5

Explanation:

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

Idea: DP

Solution 1: DP

Time complexity: O(n*sum)

Space complexity: O(n*sum)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

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

if (sum < S) return 0;

const int offset = sum;

// ways[i][j] means total ways to sum up to (j - offset) using nums[0] ~ nums[i - 1].

vector<vector<int>> ways(n + 1, vector<int>(sum + offset + 1, 0));

ways[0][offset] = 1;

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

for (int j = nums[i]; j < 2 * sum + 1 - nums[i]; ++j)

if (ways[i][j]) {

ways[i + 1][j + nums[i]] += ways[i][j];

ways[i + 1][j - nums[i]] += ways[i][j];

}

return ways.back()[S + offset];

}

};

C++ SC O(n)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

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

if (sum < std::abs(S)) return 0;

const int kOffset = sum;

const int kMaxN = sum * 2 + 1;

vector<int> ways(kMaxN, 0);

ways[kOffset] = 1;

for (int num : nums) {

vector<int> tmp(kMaxN, 0);

for (int i = num; i < kMaxN - num; ++i)

if (ways[i]) {

tmp[i + num] += ways[i];

tmp[i - num] += ways[i];

}

std::swap(ways, tmp);

}

return ways[S + kOffset];

}

};

Java

// Author: Huahua

// Running time: 28 ms

class Solution {

public int findTargetSumWays(int[] nums, int S) {

int sum = 0;

for (final int num : nums)

sum += num;

if (sum < S) return 0;

final int kOffset = sum;

final int kMaxN = sum * 2 + 1;

int[] ways = new int[kMaxN];

ways[kOffset] = 1;

for (final int num : nums) {

int[] tmp = new int[kMaxN];

for (int i = num; i < kMaxN - num; ++i) {

tmp[i + num] += ways[i];

tmp[i - num] += ways[i];

}

ways = tmp;

}

return ways[S + kOffset];

}

C++ / V2

// Author: Huahua

// Running time: 17 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

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

if (sum < std::abs(S)) return 0;

const int kOffset = sum;

const int kMaxN = sum * 2 + 1;

vector<int> ways(kMaxN, 0);

ways[kOffset] = 1;

for (int num : nums) {

vector<int> tmp(kMaxN, 0);

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

if (i + num < kMaxN) tmp[i] += ways[i + num];

if (i - num >= 0) tmp[i] += ways[i - num];

}

std::swap(ways, tmp);

}

return ways[S + kOffset];

}

};

Solution 2: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 422 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

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

if (sum < std::abs(S)) return 0;

int ans = 0;

dfs(nums, 0, S, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int d, int S, int& ans) {

if (d == nums.size()) {

if (S == 0) ++ans;

return;

}

dfs(nums, d + 1, S - nums[d], ans);

dfs(nums, d + 1, S + nums[d], ans);

}

};

Java

// Author: Huahua

// Running time: 615 ms

class Solution {

private int ans;

public int findTargetSumWays(int[] nums, int S) {

int sum = 0;

for (final int num : nums)

sum += num;

if (sum < Math.abs(S)) return 0;

ans = 0;

dfs(nums, 0, S);

return ans;

}

private void dfs(int[] nums, int d, int S) {

if (d == nums.length) {

if (S == 0) ++ans;

return;

}

dfs(nums, d + 1, S - nums[d]);

dfs(nums, d + 1, S + nums[d]);

}

Solution 3: Subset sum

Time complexity: O(n*sum)

Space complexity: O(sum)

C++ w/ copy

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

S = std::abs(S);

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

if (sum < S || (S + sum) % 2 != 0) return 0;

const int target = (S + sum) / 2;

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

dp[0] = 1;

for (int num : nums) {

vector<int> tmp(dp);

for (int j = 0; j <= target - num; ++j)

tmp[j + num] += dp[j];

std::swap(dp, tmp);

}

return dp[target];

}

};

C++ w/o copy

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

S = std::abs(S);

const int n = nums.size();

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

if (sum < S || (S + sum) % 2 != 0) return 0;

const int target = (S + sum) / 2;

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

dp[0] = 1;

for (int num : nums)

for (int j = target; j >= num; --j)

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

return dp[target];

}

};