Posts tagged as “counting”

花花酱 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 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 730. Count Different Palindromic Subsequences

By zxi on November 20, 2017

Problem:

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7.

A subsequence of a string S is obtained by deleting 0 or more characters from S.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences A_1, A_2, ... and B_1, B_2, ... are different if there is some i for which A_i != B_i.

Example 1:

Input: 
S = 'bccb'
Output: 6
Explanation: 
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

Example 2:

Input: 
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
Output: 104860361
Explanation: 
There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.

Note:

The length of S will be in the range [1, 1000].
Each character S[i] will be in the set {'a', 'b', 'c', 'd'}.

Idea:

Solution 1: Recursion with memoization

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua

// Runtime: 72 ms

class Solution {

public:

int countPalindromicSubsequences(const string& S) {

const int n = S.length();

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

return count(S, 0, S.length() - 1);

}

private:

static constexpr long kMod = 1000000007;

long count(const string& S, int s, int e) {

if (s > e) return 0;

if (s == e) return 1;

if (m_[s][e] > 0) return m_[s][e];

long ans = 0;

if (S[s] == S[e]) {

int l = s + 1;

int r = e - 1;

while (l <= r && S[l] != S[s]) ++l;

while (l <= r && S[r] != S[s]) --r;

if (l > r)

ans = count(S, s + 1, e - 1) * 2 + 2;

else if (l == r)

ans = count(S, s + 1, e - 1) * 2 + 1;

else

ans = count(S, s + 1, e - 1) * 2

- count(S, l + 1, r - 1);

} else {

ans = count(S, s, e - 1)

+ count(S, s + 1, e)

- count(S, s + 1, e - 1);

}

return m_[s][e] = (ans + kMod) % kMod;

}

vector<vector<int>> m_;

};

Python

"""

Author: Huahua

Runtime: 3582 ms

"""

class Solution:

def countPalindromicSubsequences(self, S):

def count(S, i, j):

if i > j: return 0

if i == j: return 1

if self.m_[i][j]: return self.m_[i][j]

if S[i] == S[j]:

ans = count(S, i + 1, j - 1) * 2

l = i + 1

r = j - 1

while l <= r and S[l] != S[i]: l += 1

while l <= r and S[r] != S[i]: r -= 1

if l > r: ans += 2

elif l == r: ans += 1

else: ans -= count(S, l + 1, r - 1)

else:

ans = count(S, i + 1, j) + count(S, i, j - 1) - count(S, i + 1, j - 1)

self.m_[i][j] = ans % 1000000007

return self.m_[i][j]

n = len(S)

self.m_ = [[None for _ in range(n)] for _ in range(n)]

return count(S, 0, n - 1)

Java

// Author: Huahua

// Runtime: 107 ms

class Solution {

private int[][] m_;

private static final int kMod = 1000000007;

public int countPalindromicSubsequences(String S) {

int n = S.length();

m_ = new int[n][n];

return count(S.toCharArray(), 0, n - 1);

}

private int count(char[] s, int i, int j) {

if (i > j) return 0;

if (i == j) return 1;

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

long ans = 0;

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

ans += count(s, i + 1, j - 1) * 2;

int l = i + 1;

int r = j - 1;

while (l <= r && s[l] != s[i]) ++l;

while (l <= r && s[r] != s[i]) --r;

if (l > r) ans += 2;

else if (l == r) ans += 1;

else ans -= count(s, l + 1, r - 1);

} else {

ans = count(s, i, j - 1)

+ count(s, i + 1, j)

- count(s, i + 1, j - 1);

}

m_[i][j] = (int)((ans + kMod) % kMod);

return m_[i][j];

}

Solution 2: DP

C++

// Author: Huahua

// Runtime: 79 ms

class Solution {

public:

int countPalindromicSubsequences(const string& S) {

int n = S.length();

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

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

dp[i][i] = 1;

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

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

const int j = i + len;

if (S[i] == S[j]) {

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

int l = i + 1;

int r = j - 1;

while (l <= r && S[l] != S[i]) ++l;

while (l <= r && S[r] != S[i]) --r;

if (l == r) dp[i][j] += 1;

else if (l > r) dp[i][j] += 2;

else dp[i][j] -= dp[l + 1][r - 1];

} else {

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

}

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

}

return dp[0][n - 1];

}

private:

static constexpr long kMod = 1000000007;

};

Pyhton

"""

Author: Huahua

Runtime: 3639 ms

"""

class Solution:

def countPalindromicSubsequences(self, S):

n = len(S)

if n == 0: return 0

dp = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n): dp[i][i] = 1

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

for i in range(n - size + 1):

j = i + size - 1

if S[i] == S[j]:

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

l = i + 1

r = j - 1

while l <= r and S[l] != S[i]: l += 1

while l <= r and S[r] != S[i]: r -= 1

if l > r: dp[i][j] += 2

elif l == r: dp[i][j] += 1

else: dp[i][j] -= dp[l + 1][r - 1]

else:

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

dp[i][j] %= 1000000007

return dp[0][n - 1]

Related Problems:

[解题报告] LeetCode 664. Strange Printer

花花酱 LeetCode 639. Decode Ways II

By zxi on November 18, 2017

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping way:

'A' -> 1

'B' -> 2

...

'Z' -> 26

Beyond that, now the encoded string can also contain the character ‘*’, which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character ‘*’, return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod 10⁹ + 7.

Example 1:

Input: "*"

Output: 9

Explanation: The encoded message can be decoded to the string:

"A", "B", "C", "D", "E", "F", "G", "H", "I".

Example 2:

1 2	Input: "1*" Output: 9 + 9 = 18

Note:

The length of the input string will fit in range [1, 10⁵].
The input string will only contain the character ‘*’ and digits ‘0’ – ‘9’.

Idea:

Time complexity: O(n)

Space complexity: O(1)

Solution:

C++

// Author: Huahua

// Runtime: 58 ms

class Solution {

public:

int numDecodings(string s) {

if (s.empty()) return 0;

// dp[-1] dp[0]

long dp[2] = {1, ways(s[0])};

for (int i = 1; i < s.length(); ++i) {

long dp_i = ways(s[i]) * dp[1] + ways(s[i - 1], s[i]) * dp[0];

dp_i %= kMod;

dp[0] = dp[1];

dp[1] = dp_i;

}

return dp[1];

}

private:

static constexpr int kMod = 1000000007;

int ways(char c) {

if (c == '0') return 0;

if (c == '*') return 9;

return 1;

}

int ways(char c1, char c2) {

if (c1 == '*' && c2 == '*')

return 15;

if (c1 == '*') {

return (c2 >= '0' && c2 <= '6') ? 2 : 1;

} else if (c2 == '*') {

switch (c1) {

case '1': return 9;

case '2': return 6;

default: return 0;

}

} else {

int prefix = (c1 - '0') * 10 + (c2 - '0');

return prefix >= 10 && prefix <= 26;

}

};

Related Problems:

[解题报告] LeetCode 91. Decode Ways

花花酱 LeetCode 91. Decode Ways

By zxi on November 9, 2017

题目大意：

给你一个加密的数字字符串，问你一共有多少种不同的解密方式。

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Idea:

Dynamic Programming

Solution:

C++

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int numDecodings(string s) {

if(s.length() == 0) return 0;

m_ways[""] = 1;

return ways(s);

}

private:

int ways(const string& s) {

if (m_ways.count(s)) return m_ways[s];

if (s[0] == '0') return 0;

if (s.length() == 1) return 1;

int w = ways(s.substr(1));

const int prefix = stoi(s.substr(0, 2));

if (prefix <= 26)

w += ways(s.substr(2));

m_ways[s] = w;

return w;

}

unordered_map<string, int> m_ways;

};

C++

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

int numDecodings(string s) {

if(s.length() == 0) return 0;

return ways(s, 0, s.length() - 1);

}

private:

int ways(const string& s, int l, int r) {

if (m_ways.count(l)) return m_ways[l];

if (s[l] == '0') return 0;

if (l >= r) return 1; // Single digit or empty.

int w = ways(s, l + 1, r);

const int prefix = (s[l] - '0') * 10 + (s[l + 1] - '0');

if (prefix <= 26)

w += ways(s, l + 2, r);

m_ways[l] = w;

return w;

}

// Use l as key.

unordered_map<int, int> m_ways;

};

C++

Time complexity: O(n)

Space complexity: O(1)

class Solution {

public:

int numDecodings(string s) {

if (s.empty() || s[0] == '0') return 0;

if (s.length() == 1) return 1;

const int n = s.length();

int w1 = 1;

int w2 = 1;

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

int w = 0;

if (!isValid(s[i]) && !isValid(s[i - 1], s[i])) return 0;

if (isValid(s[i])) w = w1;

if (isValid(s[i - 1], s[i])) w += w2;

w2 = w1;

w1 = w;

}

return w1;

}

private:

bool isValid(const char c) { return c != '0'; }

bool isValid(const char c1, const char c2) {

const int num = (c1 - '0')*10 + (c2 - '0');

return num >= 10 && num <= 26;

}

};

Related Problems:

[解题报告] LeetCode 639. Decode Ways II – 花花酱