Posts tagged as “dp”

花花酱 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 309. Best Time to Buy and Sell Stock with Cooldown

By zxi on January 6, 2018

题目大意：给你每天的股价，没有交易次数限制，但是卖出后要休息一天才能再买进。问你最大收益是多少？

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]

maxProfit = 3

transactions = [buy, sell, cooldown, buy, sell]

Idea:

Solution:

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

int sold = 0;

int rest = 0;

int hold = INT_MIN;

for (const int price : prices) {

int prev_sold = sold;

sold = hold + price;

hold = max(hold, rest - price);

rest = max(rest, prev_sold);

}

return max(rest, sold);

}

};

Related Problems:

花花酱 LeetCode 121. Best Time to Buy and Sell Stock

花花酱 LeetCode 322. Coin Change

By zxi on January 2, 2018

题目大意：给你一些不同币值的硬币，问你最少需要多少个硬币才能组成amount，假设每种硬币有无穷多个。

Problem:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Idea:

DP /knapsack

Solution1:

C++ / DP

Time complexity: O(n*amount^2)

Space complexity: O(amount)

// Author: Huahua

// Running time: 189 ms

class Solution {

public:

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

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

dp[0] = 0;

for (auto coin : coins) {

for (int i = amount - coin; i >= 0; --i)

if (dp[i] != INT_MAX)

for (int k = 1; k * coin + i <= amount; ++k)

dp[i + k * coin] = min(dp[i + k * coin], dp[i] + k);

}

return dp[amount] == INT_MAX ? -1 : dp[amount];

}

};

Solution2:

C++ / DP

Time complexity: O(n*amount)

Space complexity: O(amount)

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

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

// dp[i] = min coins to make up to amount i

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

dp[0] = 0;

for (int coin : coins) {

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

if (dp[i - coin] != INT_MAX)

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

}

return dp[amount] == INT_MAX ? -1 : dp[amount];

}

};

Python3

"""

Author: Huahua

Running time: 632 ms beats 90.27%

"""

class Solution:

def coinChange(self, coins, amount):

INVALID = 2**32

dp = [INVALID] * (amount + 1)

dp[0] = 0

for coin in coins:

for i in range(coin, amount + 1):

if dp[i - coin] >= dp[i]: continue

dp[i] = dp[i - coin] + 1

return -1 if dp[amount] == INVALID else dp[amount]

Solution3:

C++ / DFS

Time complexity: O(amount^n/(coin_0*coin_1*…*coin_n))

Space complexity: O(n)

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

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

// Sort coins in desending order

std::sort(coins.rbegin(), coins.rend());

int ans = INT_MAX;

coinChange(coins, 0, amount, 0, ans);

return ans == INT_MAX ? -1 : ans;

}

private:

void coinChange(const vector<int>& coins,

int s, int amount, int count, int& ans) {

if (amount == 0) {

ans = min(ans, count);

return;

}

if (s == coins.size()) return;

const int coin = coins[s];

for (int k = amount / coin; k >= 0 && count + k < ans; k--)

coinChange(coins, s + 1, amount - k * coin, count + k, ans);

}

};

Python3

"""

Author: Huahua

Running time: 200ms

"""

class Solution:

def coinChange(self, coins, amount):

coins.sort(reverse=True)

INVALID = 10**10

self.ans = INVALID

def dfs(s, amount, count):

if amount == 0:

self.ans = count

return

if s == len(coins): return

coin = coins[s]

for k in range(amount // coin, -1, -1):

if count + k >= self.ans: break

dfs(s + 1, amount - k * coin, count + k)

dfs(0, amount, 0)

return -1 if self.ans == INVALID else self.ans