Posts published in “Dynamic Programming”

花花酱 LeetCode 1310. XOR Queries of a Subarray

By zxi on January 5, 2020

Given the array arr of positive integers and the array queries where queries[i] = [L_i,R_i], for each query i compute the XOR of elements from L_i to Ri (that is, arr[L_i] xor arr[L_i+1] xor ... xor arr[R_i] ). Return an array containing the result for the given queries.

Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8] 
Explanation: 
The binary representation of the elements in the array are:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
The XOR values for queries are:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

Example 2:

Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

Constraints:

1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 10^9
1 <= queries.length <= 3 * 10^4
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] < arr.length

Solution: Prefix Sum

Time complexity: O(n) + O(q)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {

// xors[i + 1] = arr[0] ^ arr[1] ^ ... ^ arr[i]

vector<int> xors(arr.size() + 1);

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

xors[i + 1] = xors[i] ^ arr[i];

}

vector<int> ans;

for (const auto& q : queries) {

const int l = q[0];

const int r = q[1];

ans.push_back(xors[r + 1] ^ xors[l]);

}

return ans;

}

};

tby

花花酱 LeetCode 1312. Minimum Insertion Steps to Make a String Palindrome

By zxi on January 4, 2020

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Example 4:

Input: s = "g"
Output: 0

Example 5:

Input: s = "no"
Output: 1

Constraints:

1 <= s.length <= 500
All characters of s are lower case English letters.

Solution: DP

dp[i][j] := min chars to insert
dp[j][j] = dp[i-1][j+1] if s[i] == s[j] else min(dp[i+1][j] , dp[i][j-1]) + 1
base case: dp[i][i] = 0
ans: dp[0][n-1]

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

C++

// Author: Huahua

class Solution {

public:

int minInsertions(string s) {

const int n = s.length();

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

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

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

dp[i][j] = s[i] == s[j] ? dp[i + 1][j - 1] : min(dp[i + 1][j], dp[i][j - 1]) + 1;

return dp[0][n - 1];

}

};

花花酱 LeetCode 1301. Number of Paths with Max Score

By zxi on December 28, 2019

You are given a square board of characters. You can move on the board starting at the bottom right square marked with the character 'S'.

You need to reach the top left square marked with the character 'E'. The rest of the squares are labeled either with a numeric character 1, 2, ..., 9 or with an obstacle 'X'. In one move you can go up, left or up-left (diagonally) only if there is no obstacle there.

Return a list of two integers: the first integer is the maximum sum of numeric characters you can collect, and the second is the number of such paths that you can take to get that maximum sum, taken modulo 10^9 + 7.

In case there is no path, return [0, 0].

Example 1:

Input: board = ["E23","2X2","12S"]
Output: [7,1]

Example 2:

Input: board = ["E12","1X1","21S"]
Output: [4,2]

Example 3:

Input: board = ["E11","XXX","11S"]
Output: [0,0]

Constraints:

2 <= board.length == board[i].length <= 100

Solution: DP

dp[i][j] := max score when reach (j, i)
count[i][j] := path to reach (j, i) with max score

m = max(dp[i + 1][j], dp[i][j+1], dp[i+1][j+1])
dp[i][j] = board[i][j] + m
count[i][j] += count[i+1][j] if dp[i+1][j] == m
count[i][j] += count[i][j+1] if dp[i][j+1] == m
count[i][j] += count[i+1][j+1] if dp[i+1][j+1] == m

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

C++

// Author: Huahua

class Solution {

public:

vector<int> pathsWithMaxScore(vector<string>& board) {

constexpr int kMod = 1e9 + 7;

const int n = board.size();

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

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

board[n - 1][n - 1] = board[0][0] = '0';

cc[n - 1][n - 1] = 1;

for (int i = n - 1; i >= 0; --i)

for (int j = n - 1; j >= 0; --j) {

if (board[i][j] != 'X') {

int m = max({dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1]});

dp[i][j] = (board[i][j] - '0') + m;

if (dp[i + 1][j] == m)

cc[i][j] = (cc[i][j] + cc[i + 1][j]) % kMod;

if (dp[i][j + 1] == m)

cc[i][j] = (cc[i][j] + cc[i][j + 1]) % kMod;

if (dp[i + 1][j + 1] == m)

cc[i][j] = (cc[i][j] + cc[i + 1][j + 1]) % kMod;

}

return {cc[0][0] ? dp[0][0] : 0, cc[0][0]};

}

};

花花酱 LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

By zxi on December 17, 2019

Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0

Example 3:

Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3

Example 4:

Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2

Constraints:

1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold <= 10^5

Solution: DP + Brute Force

Precompute the sums of sub-matrixes whose left-top corner is at (0,0).

Try all possible left-top corner and sizes.

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

C++

// Author: Huahua, 148 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

const int n = mat[0].size();

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

for (int y = 1; y <= m; ++y)

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

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

for (int y = 1; y <= m; ++y)

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

for (int k = 0; y + k <= m && x + k <= n; ++k) {

if (rangeSum(x, y, x + k, y + k) > threshold) break;

ans = max(ans, k + 1);

}

return ans;

}

};

Solution 2: Binary Search

Search for the smallest size k that is greater than the threshold, ans = k – 1.

C++

// Author: Huahua, 116 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

const int n = mat[0].size();

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

for (int y = 1; y <= m; ++y)

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

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

for (int y = 1; y <= m; ++y)

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

int l = 0;

int r = min(m - y, n - x) + 1;

while (l < r) {

int m = l + (r - l) / 2;

// Find smllest l that > threshold, ans = (l + 1) - 1

if (rangeSum(x, y, x + m, y + m) > threshold)

r = m;

else

l = m + 1;

}

ans = max(ans, (l + 1) - 1);

}

return ans;

}

};

Solution 3: Bounded Search

Time complexity: O(m*n + min(m,n))

C++

// Author: Huahua, 148 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

const int n = mat[0].size();

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

for (int y = 1; y <= m; ++y)

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

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

for (int y = 1; y <= m; ++y)

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

for (int k = ans; y + k <= m && x + k <= n; ++k) {

if (rangeSum(x, y, x + k, y + k) > threshold) break;

ans = max(ans, k + 1);

}

return ans;

}

};

花花酱 LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination

By zxi on December 14, 2019

iven a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Example 1:

Input: 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
Output: 6
Explanation: 
The shortest path without eliminating any obstacle is 10. 
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

Example 2:

Input: 
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
Output: -1
Explanation: 
We need to eliminate at least two obstacles to find such a walk.

Constraints:

grid.length == m
grid[0].length == n
1 <= m, n <= 40
1 <= k <= m*n
grid[i][j] == 0 or 1
grid[0][0] == grid[m-1][n-1] == 0

Solution: BFS

State: (x, y, k) where k is the number of obstacles along the path.

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

C++

// Author: Huahua, 8 ms, 10.5 MB

class Solution {

public:

int shortestPath(vector<vector<int>>& grid, int k) {

const vector<int> dirs{0, 1, 0, -1, 0};

const int n = grid.size();

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

vector<vector<int>> seen(n, vector<int>(m, INT_MAX));

queue<tuple<int, int, int>> q;

int steps = 0;

q.emplace(0, 0, 0);

seen[0][0] = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int cx, cy, co;

tie(cx, cy, co) = q.front(); q.pop();

if (cx == m - 1 && cy == n - 1) return steps;

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

int x = cx + dirs[i];

int y = cy + dirs[i + 1];

if (x < 0 || y < 0 || x >= m || y >= n) continue;

int o = co + grid[y][x];

if (o >= seen[y][x] || o > k) continue;

seen[y][x] = o;

q.emplace(x, y, o);

}

++steps;

}

return -1;

}

};

Solution 2: DP

Time complexity: O(mnk)
Space complexity: O(mnk)

Bottom-Up

// AC 236 ms

class Solution {

public:

int shortestPath(vector<vector<int>>& grid, int k) {

constexpr int kInf = 1e9;

const int m = grid.size();

const int n = grid[0].size();

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

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

for (int s = 0; s < 3; ++s)

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

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

const int o = grid[i - 1][j - 1];

for (int z = 0; z + o <= k; ++z)

dp[i][j][z + o] = min(dp[i][j][z + o],

min({dp[i - 1][j][z],

dp[i][j - 1][z],

dp[i + 1][j][z],

dp[i][j + 1][z]}) + 1);

}

int ans = *min_element(begin(dp[m][n]), end(dp[m][n]));

return ans >= kInf ? -1 : ans;

}

};

Top-Down

class Solution {

public:

int shortestPath(vector<vector<int>>& grid, int K) {

constexpr int kInf = 1e9;

const vector<int> dirs{0, 1, 0, -1, 0};

const int m = grid.size();

const int n = grid[0].size();

vector<vector<vector<int>>> mem(m + 2, vector<vector<int>>(n + 2, vector<int>(K + 1, -1)));

vector<vector<int>> seen(m + 2, vector<int>(n + 2));

function<int(int, int, int)> dp = [&](int x, int y, int k) {

if (x < 1 || x > n || y < 1 || y > m || k < 0 || seen[y][x]) return kInf;

if (x == 1 && y == 1) return 0;

if (mem[y][x][k] != -1) return mem[y][x][k];

seen[y][x] = 1;

int ans = kInf;

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

ans = min(ans, 1 + dp(x + dirs[i], y + dirs[i + 1], k - grid[y - 1][x - 1]));

seen[y][x] = 0;

return mem[y][x][k] = ans;

};

const int ans = dp(n, m, K);

return ans >= kInf ? -1 : ans;

}

};