LeetCode 3276: Select Cells in Grid With Maximum Score
Problem Description
Explanation:
To solve this problem, we can use dynamic programming. We will iterate over each row of the grid and maintain a list of sets representing the selected cells at each row. For each cell in the current row, we will check all possible combinations of adding the cell's value to the sets from the previous row which satisfy the conditions. We will update the sets for the current row based on the maximum score we can achieve at that position.
At the end, we will return the maximum score achievable from the last row of sets.
- Time complexity: O(m * n * 2^n), where m is the number of rows, n is the number of columns, and 2^n represents the number of possible combinations.
- Space complexity: O(m * 2^n), where m is the number of rows and 2^n represents the number of possible combinations.
:
Solutions
class Solution {
public int maxGridSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
List<Set<Integer>> dp = new ArrayList<>();
dp.add(new HashSet<>());
for (int row = 0; row < m; row++) {
List<Set<Integer>> newDp = new ArrayList<>();
for (Set<Integer> prevSet : dp) {
for (int col = 0; col < n; col++) {
Set<Integer> newSet = new HashSet<>(prevSet);
newSet.add(grid[row][col]);
newDp.add(newSet);
}
}
dp = newDp;
}
int maxScore = 0;
for (Set<Integer> set : dp) {
int score = set.stream().mapToInt(Integer::intValue).sum();
maxScore = Math.max(maxScore, score);
}
return maxScore;
}
}Loading editor...