[JAVA] - For Beginners - Detailed explanation - Brute force to Memoization
Approach\n\n Start recursion from start location, go to all possible locations repeat it until fuel is negative.\n If finish is reached add 1 to the count of pa
**Approach**\n\n* Start recursion from start location, go to all possible locations repeat it until fuel is negative.\n* If finish is reached add 1 to the count of paths.\n\n\nIf you look at the recursion tree, text in orange indicates fuel available at location. Use this combination to memoize. Location-fuel at that point.\n![image](https://assets.leetcode.com/users/images/37c14738-e223-431c-bb28-8ef07590d245_1599405670.4378273.png)\n\n\n**Brute force**\n```\nclass Solution {\n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        long res = count(locations,start,finish,fuel);\n        return (int)res;\n    }\n    \n    public long count(int[] locations, int curr, int finish, int fuel){\n        if(fuel<0) return 0; //Cannot go further.\n        long res = 0;\n        if(curr==finish) res = 1; //Should not return, cos you can still travel as long as fuel is available.\n        for(int i=0;i<locations.length;i++){\n            if(i==curr) continue; //Don\'t visit the same location.\n            if(fuel < Math.abs(locations[curr]-locations[i])) continue; //Can\'t travel if fuel is less.\n            res+=(count(locations,i,finish,(fuel - Math.abs(locations[i]-locations[curr])))%1000000007);\n        }\n       return res;\n    }\n}\n```\n\n**With memoization**\n```\nclass Solution {\n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        long[][] dp = new long[locations.length][fuel+1];\n        for(int i=0;i<dp.length;i++) Arrays.fill(dp[i],-1l);\n        return (int) count(locations,start,finish,fuel,dp);\n    }\n    \n    public long count(int[] locations, int curr, int finish, int fuel,long[][] dp){\n        if(fuel<0) return 0;\n        if(dp[curr][fuel]!=-1) return dp[curr][fuel];\n        long res = 0;\n        if(curr==finish) res = 1;\n        for(int i=0;i<locations.length;i++){\n            if(i==curr) continue;\n            int fuelAft = (fuel - Math.abs(locations[i]-locations[curr]));\n            res=(res + count(locations,i,finish,fuelAft,dp))%1000000007;\n        }\n        dp[curr][fuel] =  res;\n        return res;\n    }\n}\n```
[]