aboutsummaryrefslogtreecommitdiff
path: root/brainpower.py
diff options
context:
space:
mode:
Diffstat (limited to 'brainpower.py')
-rw-r--r--brainpower.py30
1 files changed, 30 insertions, 0 deletions
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]]))