Leetcode Problem:
Summary
- Given a 2D array of questions where each question has a point value and a brainpower value, find the maximum points that can be earned by solving the questions in order.
Approach
- Dynamic Programming: The problem can be solved using dynamic programming
- The idea is to maintain a memoization table to store the maximum points that can be earned for each question
- The function iterates over the questions in reverse order and for each question, it calculates the maximum points that can be earned by either solving the current question or skipping it.
Complexity
- O(N) where N is the number of questions, as each question is visited once.
Solution Code:
class Solution {
public:
long long memo[200001] = {0};
long long mostPoints(vector>& questions) {
int N = questions.size();
for(int i = N - 1; i >= 0; i--){
int point = questions[i][0];
int brainpower = questions[i][1];
memo[i] = max(point + memo[i + brainpower + 1], memo[i+1]);
}
return memo[0];
}
};
class Solution {
public:
long long memo[200001] = {0};
long long mostPoints(vector>& questions) {
int N = questions.size();
for(int i = N - 1; i >= 0; i--){
int point = questions[i][0];
int brainpower = questions[i][1];
memo[i] = max(point + memo[i + brainpower + 1], memo[i+1]);
}
return memo[0];
}
};
'알고리즘' 카테고리의 다른 글
| Put Marbles in Bags (0) | 2025.04.01 |
|---|---|
| Partition Labels (0) | 2025.03.30 |
| Apply Operations to Maximize Score (0) | 2025.03.29 |
| Maximum Number of Points From Grid Queries (0) | 2025.03.28 |
| Minimum Index of a Valid Split (0) | 2025.03.28 |
짬뽕얼큰하게