Java || Recursion + Memoization + Bottom Up || beats 97% || T.C - O(N^2*F) S.C - O(N*F)
\n\t// O(locations.length^fuel) O(fuel)\n\t// Recursion\n\tpublic int countRoutesRec(int[] locations, int start, int finish, int fuel) {\n\n\t\tint len = locati
\n\t// O(locations.length^fuel) O(fuel)\n\t// Recursion\n\tpublic int countRoutesRec(int[] locations, int start, int finish, int fuel) {\n\n\t\tint len = locations.length, mod = 1_000_000_007;\n\t\treturn countRoutesRecHelper(locations, start, finish, fuel, len, mod);\n\t}\n\n\t// O(locations.length^fuel) O(fuel)\n\t// Recursion\n\tpublic int countRoutesRecHelper(int[] locations, int curr, int finish, int fuel, int len, int mod) {\n\n\t\tif (fuel == 0 && curr == finish)\n\t\t\treturn 1;\n\n\t\tif (fuel <= 0)\n\t\t\treturn 0;\n\n\t\tboolean flag = (curr == finish) ? true : false;\n\n\t\tint ans = 0;\n\t\tfor (int i = 0; i < len; i++) {\n\t\t\tif (curr != i)\n\t\t\t\tans = (int) (((long) ans + countRoutesRecHelper(locations, i, finish,\n\t\t\t\t\t\tfuel - Math.abs(locations[curr] - locations[i]), len, mod)) % mod);\n\t\t}\n\n\t\treturn ans + ((flag) ? 1 : 0);\n\t}\n\n\t// O(locations.length^2*fuel) O(locations.length*fuel)\n\t// Memoization\n\tpublic int countRoutesMemo(int[] locations, int start, int finish, int fuel) {\n\n\t\tint len = locations.length, mod = 1_000_000_007;\n\t\tInteger[][] memo = new Integer[101][fuel + 1];\n\t\treturn countRoutesMemoHelper(locations, start, finish, fuel, len, mod, memo);\n\t}\n\n\t// O(locations.length^2*fuel) O(locations.length*fuel)\n\t// Memoization\n\tpublic int countRoutesMemoHelper(int[] locations, int curr, int finish, int fuel, int len, int mod,\n\t\t\tInteger[][] memo) {\n\n\t\tif (memo[curr][fuel] != null)\n\t\t\treturn memo[curr][fuel];\n\n\t\tboolean flag = (curr == finish) ? true : false;\n\n\t\tlong ans = 0;\n\t\tfor (int i = 0; i < len; i++) {\n\t\t\tif (curr != i && Math.abs(locations[curr] - locations[i]) <= fuel) {\n\t\t\t\tans += countRoutesMemoHelper(locations, i, finish, fuel - Math.abs(locations[curr] - locations[i]), len,\n\t\t\t\t\t\tmod, memo);\n\t\t\t}\n\t\t}\n\n\t\tmemo[curr][fuel] = (int) (ans % mod) + ((flag) ? 1 : 0);\n\t\treturn memo[curr][fuel];\n\t}\n\n\t// O(locations.length^2*fuel) O(locations.length*fuel)\n\t// Bottom Up\n\tpublic int countRoutesBU(int[] locations, int start, int finish, int fuel) {\n\n\t\tint len = locations.length, mod = 1_000_000_007;\n\t\tint[][] dp = new int[len][fuel + 1];\n\t\tdp[finish][0] = 1;\n\n\t\tfor (int j = 1; j <= fuel; j++) {\n\t\t\tfor (int i = len - 1; i >= 0; i--) {\n\t\t\t\tint ans = 0;\n\t\t\t\tfor (int k = 0; k < len; k++) {\n\t\t\t\t\tif (j - Math.abs(locations[i] - locations[k]) < 0 || k == i)\n\t\t\t\t\t\tcontinue;\n\t\t\t\t\tans = (int) (((long) ans + dp[k][j - Math.abs(locations[i] - locations[k])]) % mod);\n\t\t\t\t}\n\t\t\t\tdp[i][j] = ans + ((i == finish) ? 1 : 0);\n\t\t\t}\n\t\t}\n\n\t\treturn dp[start][fuel];\n\t}
[]