content: package dynamicprogramming;
  
  public class GameScoring {
  
      /*
       * Imagine a game (like cricket) where a player can score 1,2 or 4 runs.
       * Given a score "n", find the total number of ways score "n" can be reached.
       *
       * Runtime Complexity:
       * Linear, O(n)
       *
       * Memory Complexity:
       * Linear, O(n).
       *
       * Use the memoization technique:
       * Memoization is an optimization technique used to make programs faster and improve their performance
       * by storing the results of expensive function calls and returning the cached result when the same
       * inputs occur again. It saves the computed results for possible later reuse, rather than recomputing
       * them.
       *
       * The scoring options are 1, 2, 4. To find the number of ways a player can score 'n' runs,
       * the recurrence relation is as follows:
       * S(n) = S(n-1) + S(n-2) + S(n-4)S(n)=S(n−1)+S(n−2)+S(n−4)
       *
       *
       * */
  
      private static int scoringOptionsRec(int n, int[] result) {
          if(n < 0) return 0;
  
          if(result[n] > 0) return result[n];
  
          //Memoize
          result[n] = scoringOptionsRec(n-1, result) +
                  scoringOptionsRec(n-2, result) +
                  scoringOptionsRec(n-4, result);
  
          return result[n];
      }
  
      protected static int scoringOptions(int n) {
          if(n <= 0) return 0;
  
          int[] result = new int[n+1];
          result[0] = 1;
  
          scoringOptionsRec(n, result);
          return result[n];
      }
  
  
      public static void main(String[] args) {
          System.out.println( "Scoring Options(4): "+ scoringOptions(4)); //6
          System.out.println( "Scoring Options(5): "+ scoringOptions(5)); //10
      }
  }
  