diff options
author | Jack Sangdahl <[email protected]> | 2025-03-31 20:24:42 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-31 20:24:42 -0600 |
commit | b957ec3ee381247dc62dbbffcabcc4badf1235db (patch) | |
tree | 9cdeae179d38e56bb9e2d11307331a8164b2326e | |
parent | e1b13ac0df29496c79403cbe20c64a3c7eb414b7 (diff) | |
download | leetcode-b957ec3ee381247dc62dbbffcabcc4badf1235db.tar.gz leetcode-b957ec3ee381247dc62dbbffcabcc4badf1235db.zip |
2140. solving questions with brainpower
-rw-r--r-- | brainpower.c | 28 | ||||
-rw-r--r-- | brainpower.py | 30 |
2 files changed, 44 insertions, 14 deletions
diff --git a/brainpower.c b/brainpower.c index dc414bb..5bff250 100644 --- a/brainpower.c +++ b/brainpower.c @@ -1,7 +1,5 @@ // 2140. Solving Questions With Brainpower -#include <math.h> -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * given a 0-indexed 2d integer array 'questions' where 'questions[i] = @@ -11,15 +9,14 @@ * will earn you 'pointsi' points, but you will be unable to solve each of the * next 'brainpoweri' questions. if you skip question 'i', yo get to make the * decision on the next question. return maximum points you can score. - * */ -long long mostPoints(int **questions, int questions_size, - int *questions_col_size) { - long long *dp = malloc((questions_size + 1) * sizeof(long long)); - dp[questions_size] = 0; - for (int i = questions_size - 1; i >= 0; i--) { - int k = fmin(i + questions[i][1] + 1, questions_size); +long long mostPoints(int **questions, int questionsSize, + int *questionsColSize) { + long long *dp = (long long *)malloc((questionsSize + 1) * sizeof(long long)); + dp[questionsSize] = 0; + for (int i = questionsSize - 1; i >= 0; i--) { + int k = fmin(i + questions[i][1] + 1, questionsSize); dp[i] = fmax(questions[i][0] + dp[k], dp[i + 1]); } long long ans = dp[0]; @@ -28,8 +25,11 @@ long long mostPoints(int **questions, int questions_size, } int main() { - int q1[4][2] = {{3, 2}, {4, 3}, {4, 4}, {2, 5}}, qs1 = 4, qcs1[] = {}; - int q2[5][2] = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}, qs2 = 5, qcs2[] = {}; - printf("%lld\n", mostPoints(q1, qs1, qcs1)); // expect: 5 - printf("%lld\n", mostPoints(q2, qs2, qcs2)); // expect: 7 + int q1i[4][2] = {{3, 2}, {4, 3}, {4, 4}, {2, 5}}, + q2i[5][2] = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + struct two_d_arr q1, q2; + two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i); + two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i); + printf("%lld\n", mostPoints(q1.arr, q1.row_size, q1.col_size)); // expect: 5 + printf("%lld\n", mostPoints(q2.arr, q2.row_size, q2.col_size)); // expect: 7 } diff --git a/brainpower.py b/brainpower.py new file mode 100644 index 0000000..24c149c --- /dev/null +++ b/brainpower.py @@ -0,0 +1,30 @@ +# 2140. Solving Questions With Brainpower + +""" +given a 0-indexed 2d integer array 'questions' where 'questions[i] = +[pointsi, brainpoweri]'. the array describes the questions of an exam, where +you have to process the questions in order (ie starting from question 0) and +make a decision whether to solve or skip each question. solving question 'i' +will earn you 'pointsi' points, but you will be unable to solve each of the +next 'brainpoweri' questions. if you skip question 'i', yo get to make the +decision on the next question. return maximum points you can score. +""" + + +class Solution(object): + def mostPoints(self, questions): + """ + :type questions: List[List[int]] + :rtype: int + """ + dp = [0] * (len(questions) + 1) + for i in range(len(questions) - 1, -1, -1): + points, jump = questions[i][0], questions[i][1] + dp[i] = max(points + dp[min(jump + i + 1, len(questions))], dp[i + 1]) + return dp[0] + + +if __name__ == "__main__": + obj = Solution() + print(obj.mostPoints(questions=[[3, 2], [4, 3], [4, 4], [2, 5]])) + print(obj.mostPoints(questions=[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]])) |