LeetCode 1659: Maximize Grid Happiness
Problem Description
Explanation:
To solve this problem, we can use dynamic programming with bitmasking to keep track of the state of the grid and the types of people assigned to each cell. We can iterate through all possible combinations of assigning introverts and extroverts to each cell and calculate the happiness accordingly.
The key idea is to define a state for each cell indicating whether it is empty, assigned to an introvert, or assigned to an extrovert. We can then iterate through all possible states of the grid and for each state, calculate the happiness based on the neighbors and the type of person assigned to each cell.
By memoizing the results for each state, we can avoid recalculating the same states multiple times, which helps in reducing the time complexity of the solution.
Time Complexity:
The time complexity of this solution is O(3^(mn) * m * n) where 3^(mn) represents the number of possible states for each cell in the grid.
Space Complexity:
The space complexity of this solution is O(3^(m*n)) to store the memoization table.
: :
Solutions
class Solution {
public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
int[][][] dp = new int[m * n + 1][introvertsCount + 1][extrovertsCount + 1];
return dfs(0, m, n, introvertsCount, extrovertsCount, 0, dp);
}
private int dfs(int idx, int m, int n, int intro, int extro, int state, int[][][] dp) {
if (idx == m * n) {
return 0;
}
if (dp[idx][intro][extro] != 0) {
return dp[idx][intro][extro];
}
int r = idx / n, c = idx % n;
int res = 0;
// Skip assigning anyone to this cell
res = dfs(idx + 1, m, n, intro, extro, state / 3, dp);
// Assign introvert
if (intro > 0) {
int cur = 120;
if (r > 0 && (state % 3) == 1) cur -= 30;
if (c > 0 && (state % 3) == 1) cur -= 30;
res = Math.max(res, cur + dfs(idx + 1, m, n, intro - 1, extro, (state * 3) % 9 + 1, dp));
}
// Assign extrovert
if (extro > 0) {
int cur = 40;
if (r > 0 && (state % 3) == 2) cur -= 30;
if (c > 0 && (state % 3) == 2) cur -= 30;
res = Math.max(res, cur + dfs(idx + 1, m, n, intro, extro - 1, (state * 3) % 9 + 2, dp));
}
dp[idx][intro][extro] = res;
return res;
}
}Loading editor...