leetcode

commit 5bfd5701a7cb83bb1633ab6d6c156fcb8b052102
parent 8ac85b2be8816411f74095bf192c5f89fe81b90d
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Thu, 11 May 2023 21:56:45 -0500

Optimized solution to use memoization

Diffstat:
A
solving-questions-with-brainpower/solving-questions-with-brainpowerV2.dart
 | 
38
++++++++++++++++++++++++++++++++++++++

1 file changed, 38 insertions(+), 0 deletions(-)
diff --git a/solving-questions-with-brainpower/solving-questions-with-brainpowerV2.dart b/solving-questions-with-brainpower/solving-questions-with-brainpowerV2.dart
@@ -0,0 +1,38 @@
+//This is a better versioni of the previous algorithm 
+//that uses memoization so if a question has been answered
+//before and the points that the sequence that one used is higher
+//then the current one will stop. (I.e. memoization).
+
+
+class Solution {
+  int max_points = 0;
+  List<List<int>> questions = [];
+  List<int> question_max_score = [];
+  int mostPoints(List<List<int>> question_list) {
+      for(int i = 0 ; i < question_list.length ; ++i){
+          question_max_score.add(0);
+      }
+      questions = question_list;
+      recurse(0 , 0);
+      return max_points;
+  }
+  void recurse(int points , int question_number){
+
+        if(points > max_points){
+            max_points = points;
+        }
+        if(questions.length <= question_number){
+            return;
+        }
+        if(question_max_score[question_number] > points){
+            return;
+        }
+        else{
+            question_max_score[question_number] = points;
+        }
+        int point_val= questions[question_number][0];
+        int bp = questions[question_number][1];
+        recurse(points, question_number + 1);
+        recurse(points + point_val, question_number + bp + 1);
+    }
+}