Posts tagged as “dp”

花花酱 LeetCode 1278. Palindrome Partitioning III

By zxi on December 2, 2019

You are given a string s containing lowercase letters and an integer k. You need to :

First, change some characters of s to other lowercase English letters.
Then divide s into k non-empty disjoint substrings such that each substring is palindrome.

Return the minimal number of characters that you need to change to divide the string.

Example 1:

Input: s = "abc", k = 2
Output: 1
Explanation: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

Example 2:

Input: s = "aabbc", k = 3
Output: 0
Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3:

Input: s = "leetcode", k = 8
Output: 0

Constraints:

1 <= k <= s.length <= 100.
s only contains lowercase English letters.

Solution: DP

dp[i][k] := min changes to make s[0~i] into k palindromes
dp[i][k] = min(dp[j][k – 1] + cost(j + 1, i)) 0 <= j < i

ans = dp[n-1][K]

Time complexity: O(n^2 * K) = O(n^3)
Space complexity: O(n*n + n*K) = O(n^2)

C++

// Author: Huahua, 8 ms, 9.1 MB

class Solution {

public:

int palindromePartition(string s, int K) {

const int n = s.length();

auto minChange = [&](int i, int j) {

int c = 0;

while (i < j)

if (s[i++] != s[j--]) ++c;

return c;

};

vector<vector<int>> cost(n, vector<int>(n));

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

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

cost[i][j] = minChange(i, j);

// dp[i][j] := min changes to make s[0~i] into k palindromes

vector<vector<int>> dp(n, vector<int>(K + 1, INT_MAX / 2));

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

dp[i][1] = cost[0][i];

for (int k = 1; k <= K; ++k)

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

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

}

return dp[n - 1][K];

}

};

C++/DP+DP

// Author: Huahua, 4 ms, 9.1MB

class Solution {

public:

int palindromePartition(string s, int K) {

const int n = s.length();

vector<vector<int>> cost(n, vector<int>(n));

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

for (int i = 0, j = l - 1; j < n; ++i, ++j)

cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];

vector<vector<int>> dp(n, vector<int>(K + 1, INT_MAX / 2));

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

dp[i][1] = cost[0][i];

for (int k = 2; k <= K; ++k)

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

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

}

return dp[n - 1][K];

}

};

Python3

// Author: Huahua

import functools

class Solution:

def palindromePartition(self, s: str, K: int) -> int:

@functools.lru_cache(None)

def cost(i: int, j: int) -> int:

if i >= j: return 0

return cost(i + 1, j - 1) + (1 if s[i] != s[j] else 0)

@functools.lru_cache(None)

def dp(i: int, k: int) -> int:

if k == 1: return cost(0, i)

if k == i + 1: return 0

if k > i + 1: return 1**9

return min([dp(j, k - 1) + cost(j + 1, i) for j in range(i)])

return dp(len(s) - 1, K)

花花酱 LeetCode 1277. Count Square Submatrices with All Ones

By zxi on December 1, 2019

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

Solution: DP

dp[i][j] := edge of largest square with bottom right corner at (i, j)
dp[i][j] = min(dp[i – 1][j], dp[i – 1][j – 1], dp[i][j – 1]) if m[i][j] == 1 else 0
ans = sum(dp)

Time complexity: O(n*m)
Space complexity: O(n*m)

C++

// Author: Huahua

class Solution {

public:

int countSquares(vector<vector<int>>& matrix) {

const int n = matrix.size();

const int m = matrix[0].size();

// dp[i][j] := edge of largest square with right bottom corner at (i, j)

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

int ans = 0;

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

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

dp[i][j] = matrix[i][j];

if (i && j && dp[i][j])

dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;

ans += dp[i][j];

}

return ans;

}

};

花花酱 LeetCode 1262. Greatest Sum Divisible by Three

By zxi on November 26, 2019

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

Constraints:

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

Solution: DP

dp[i] := max sum that has a remainder i when mod 3.

dp[(i + num) % 3] = max( dp[(i + num) % 3] , dp[i] + num)

ans: dp[0]

C++

// Author: Huahua

class Solution {

public:

int maxSumDivThree(vector<int>& nums) {

vector<int> dp(3);

for (int num : nums) {

vector<int> tmp(dp);

for (int s : tmp)

dp[(s + num) % 3] = max(dp[(s + num) % 3], s + num);

}

return dp[0];

}

};

花花酱 LeetCode 1269. Number of Ways to Stay in the Same Place After Some Steps

By zxi on November 24, 2019

You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

Example 2:

Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

Example 3:

Input: steps = 4, arrLen = 2
Output: 8

Constraints:

1 <= steps <= 500
1 <= arrLen <= 10^6

Solution: DP

Since we can move at most steps, we can reduce the arrLen to min(arrLen, steps + 1).

dp[i][j] = dp[i-1][j – 1] + dp[i-1][j] + dp[i-1][j+1] // sum of right, stay, left

Time complexity: O(steps * steps)
Space complexity: O(steps)

C++

// Author: Huahua

class Solution {

public:

int numWays(int steps, int arrLen) {

const int kMod = 1e9 + 7;

arrLen = min(steps + 1, arrLen);

vector<int> dp(arrLen);

dp[0] = 1;

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

vector<int> tmp(dp.size());

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

tmp[j] = dp[j];

if (j > 0) tmp[j] = (tmp[j] + dp[j - 1]) % kMod;

if (j < arrLen - 1) tmp[j] = (tmp[j] + dp[j + 1]) % kMod;

}

swap(dp, tmp);

}

return dp[0];

}

};

花花酱 LeetCode 1240. Tiling a Rectangle with the Fewest Squares

By zxi on October 27, 2019

Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.

Example 1:

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)

Example 2:

Input: n = 5, m = 8
Output: 5

Example 3:

Input: n = 11, m = 13
Output: 6

Solution1: DP + Cheating

DP can not handle case 3, for m, n <= 13, (11,13) is the only case of that special case.

dp[i][j] := min squares to tile a i x j rectangle.

dp[i][i] = 1

dp[i][j] = min(dp[r][j] + dp[i-r][j], dp[i][c] + dp[i][j – c]), 1 <= r <= i/2, 1 <= c <= j /2

answer dp[m][n]

Time complexity: O(m*n*max(n, m))
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int tilingRectangle(int n, int m) {

if (max(n, m) == 13 && min(n, m) == 11) return 6;

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

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

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

dp[i][j] = INT_MAX;

if (i == j) {

dp[i][j] = 1;

continue;

}

for (int r = 1; r <= i / 2; ++r)

dp[i][j] = min(dp[i][j], dp[r][j] + dp[i - r][j]);

for (int c = 1; c <= j / 2; ++c)

dp[i][j] = min(dp[i][j], dp[i][c] + dp[i][j - c]);

}

return dp[n][m];

}

};

Solution 2: DFS

C++

// Author: Huahua

class Solution {

public:

int tilingRectangle(int n, int m) {

if (n > m) return tilingRectangle(m, n);

int ans = n * m;

vector<int> h(n);

function<void(int)> dfs = [&](int cur) {

if (cur >= ans) return;

auto it = min_element(begin(h), end(h));

if (*it == m) { // All filled

ans = cur;

return;

}

int low = *it;

int s = it - begin(h);

int e = s;

// Find the base

while (e < n && h[e] == h[s] && (e - s + 1 + low) <= m) ++e;

for (int i = --e; i >= s; --i) {

// Try all possible square sizes in reverse order.

int size = i - s + 1;

for (int j = s; j <= i; ++j) h[j] += size;

dfs(cur + 1);

for (int j = s; j <= i; ++j) h[j] -= size;

}

};

dfs(0);

return ans;

}

};