Posts tagged as “dp”

花花酱 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;

}

};

花花酱 LeetCode 1289. Minimum Falling Path Sum II

By zxi on December 14, 2019

Given a square grid of integers arr, a falling path with non-zero shifts is a choice of exactly one element from each row of arr, such that no two elements chosen in adjacent rows are in the same column.

Return the minimum sum of a falling path with non-zero shifts.

Example 1:

Input: arr = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation: 
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.

Constraints:

1 <= arr.length == arr[i].length <= 200
-99 <= arr[i][j] <= 99

Solution: DP

dp[i][j] = min(dp[i-1][k]), 1 <= k <= m, k != j

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

C++

// Author: Huahua

class Solution {

public:

int minFallingPathSum(vector<vector<int>>& arr) {

constexpr int kInf = 1e6;

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

for (int j = 0; j < arr[0].size(); ++j) {

int m = kInf;

for (int k = 0; k < arr[0].size(); ++k) {

if (k == j) continue;

m = min(m, arr[i - 1][k]);

}

arr[i][j] += m;

}

return *min_element(begin(arr.back()), end(arr.back()));

}

};

花花酱 LeetCode 132. Palindrome Partitioning II

By zxi on December 7, 2019

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution: DP

dp[i] := min cuts of s[0~i]
dp[i] = min{dp[j] + 1} if s[j+1~i] is a palindrome.

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

C++

// Author: Huahua

class Solution {

public:

int minCut(string s) {

const int n = s.length();

// valid[i][j] = 1 if s[i~j] is palindrome, otherwise 0

vector<vector<int>> valid(n, vector<int>(n, 1));

// dp[i] = min cuts of s[0~i]

vector<int> dp(n, n);

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

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

valid[i][j] = s[i] == s[j] && valid[i + 1][j - 1];

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

if (valid[0][i]) {

dp[i] = 0;

continue;

}

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

if (valid[j + 1][i])

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

}

return dp[n - 1];

}

};

DP v2

C++

// Author: Huahua

class Solution {

public:

int minCut(string s) {

const int n = s.length();

// dp[i] = min cuts of s[0~i]

vector<int> dp(n, n);

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

for (int d = 0; d <= 1; ++d)

for (int i = m, j = m + d; i >= 0 && j < n && s[i] == s[j]; --i, ++j)

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

return dp[n - 1];

}

};

Posts tagged as “dp”

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

Solution: DP

C++

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

Solution: DP + Brute Force

C++

Solution 2: Binary Search

C++

Solution 3: Bounded Search

C++

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

Solution: BFS

C++

Solution 2: DP

Bottom-Up

Top-Down

花花酱 LeetCode 1289. Minimum Falling Path Sum II

Solution: DP

C++

花花酱 LeetCode 132. Palindrome Partitioning II

Solution: DP

C++

C++

Related Problems