[JAVA] 2 DP approaches from naive recursive to tabulation
second approach - using n, and find maximum for every i from 1 to n\n\n/**\n * naive recursive using n\n * time = 2 ^ n ?\n */\npublic long maxTaxiEarnings7(int
**second approach - using n, and find maximum for every i from 1 to n**\n```\n/**\n * naive recursive using n\n * time = 2 ^ n ?\n */\npublic long maxTaxiEarnings7(int n, int[][] rides) {\n\treturn helper(rides, n, 0);\n}\n\nprivate long helper(int[][] rides, int n, int curPoint) {\n\tif (curPoint == n)\n\t\treturn 0;\n\tlong include = 0;\n\tfor (int i = 0; i < rides.length; i++) {\n\t\tif (rides[i][0] == curPoint) {\n\t\t\tint[] ride = rides[i];\n\t\t\tinclude = Math.max(include, ride[1] - ride[0] + ride[2] + helper(rides, n, ride[1]));\n\t\t}\n\t}\n\tlong exclude = helper(rides, n, curPoint + 1);\n\treturn Math.max(include, exclude);\n}\n```\n```\n/**\n * bottom up tabulation\n * time = m * n, where m = rides.length\n */\npublic long maxTaxiEarnings8(int n, int[][] rides) {\n\tlong[] dp = new long[n + 1];\n\tfor (int curPoint = n - 1; curPoint >= 0; curPoint--) {\n\t\tlong include = 0;\n\t\tfor (int i = 0; i < rides.length; i++) {\n\t\t\tif (rides[i][0] == curPoint) {\n\t\t\t\tint[] ride = rides[i];\n\t\t\t\tinclude = Math.max(include, ride[1] - ride[0] + ride[2] +\n\t\t\t\t\t\tdp[ride[1]]);\n\t\t\t}\n\t\t}\n\t\tlong exclude = dp[curPoint + 1];\n\t\tdp[curPoint] = Math.max(include, exclude);\n\t}\n\treturn dp[0];\n}\n```\n```\n/**\n * bottom up tabulation with time optimization\n * time = m * log(m) + m + n\n *      from maxTaxiEarnings8, we see that we have an inner for-loop\n *      for finding all the rides that start at curPoint, however,\n *      if we sort rides, then we don\'t have to iterate through all the\n *      rides again, we just need to keep a pointer for rides that goes\n *      in decreasing order\n */\npublic long maxTaxiEarnings9(int n, int[][] rides) {\n\tArrays.sort(rides, (o1, o2) -> Integer.compare(o1[0], o2[0]));\n\tlong[] dp = new long[n + 1];\n\tint curRide = rides.length - 1;\n\tfor (int curPoint = n - 1; curPoint >= 0; curPoint--) {\n\t\tlong include = 0;\n\t\twhile (curRide >= 0 && rides[curRide][0] == curPoint) {\n\t\t\tint[] ride = rides[curRide];\n\t\t\tinclude = Math.max(include, ride[1] - ride[0] + ride[2] +\n\t\t\t\t\tdp[ride[1]]);\n\t\t\tcurRide--;\n\t\t}\n\t\tlong exclude = dp[curPoint + 1];\n\t\tdp[curPoint] = Math.max(include, exclude);\n\t}\n\treturn dp[0];\n}\n```\n\n\n**first approach - only using an index for rides**\n```\n/**\n * naive recursive\n * time = 2 ^ m * m, where m = rides.length\n *      2 ^ m = include or exclude\n *      m = cost of findNextAvailableRide\n */\npublic long maxTaxiEarnings4(int n, int[][] rides) {\n\tArrays.sort(rides, (o1, o2) -> Integer.compare(o1[0], o2[0]));\n\treturn helper(rides, 0);\n}\n\nprivate long helper(int[][] rides, int idx) {\n\tif (idx == rides.length)\n\t\treturn 0;\n\tint[] curRide = rides[idx];\n\tint nextAvailableRide = findNextAvailableRide(rides, idx, curRide[1]);\n\tlong include = curRide[1] - curRide[0] + curRide[2]\n\t\t\t+ helper(rides, nextAvailableRide);\n\tlong exclude = helper(rides, idx + 1);\n\treturn Math.max(include, exclude);\n}\n\nprivate int findNextAvailableRide(int[][] rides, int cur, int preEnd) {\n\tfor (int i = cur + 1; i < rides.length; i++) {\n\t\tif (rides[i][0] >= preEnd)\n\t\t\treturn i;\n\t}\n\treturn rides.length;\n}\n```\n```\n/**\n * dp bottom up\n * time = m * m, where m = rides.length\n *      first m = for loop\n *      second m = cost of findNextAvailableRide\n * space = m\n */\npublic long maxTaxiEarnings5(int n, int[][] rides) {\n\tArrays.sort(rides, (o1, o2) -> Integer.compare(o1[0], o2[0]));\n\tint m = rides.length;\n\tlong[] dp = new long[m + 1];\n\tfor (int idx = m - 1; idx >= 0; idx--) {\n\t\tint[] curRide = rides[idx];\n\t\tint nextAvailableRide = findNextAvailableRide(rides, idx, curRide[1]);\n\t\tlong include = curRide[1] - curRide[0] + curRide[2] + dp[nextAvailableRide];\n\t\tlong exclude = dp[idx + 1];\n\t\tdp[idx] = Math.max(include, exclude);\n\t}\n\treturn dp[0];\n}\n```\n```\n/**\n * dp bottom up using binary search\n * time = m * log(m)\n *      m = for loop\n *      log(m) = cost of findNextAvailableRideBS\n */\npublic long maxTaxiEarnings6(int n, int[][] rides) {\n\tArrays.sort(rides, (o1, o2) -> Integer.compare(o1[0], o2[0]));\n\tint m = rides.length;\n\tlong[] dp = new long[m + 1];\n\tfor (int idx = m - 1; idx >= 0; idx--) {\n\t\tint[] curRide = rides[idx];\n\t\tint nextAvailableRide = findNextAvailableRideBS(rides, idx, curRide[1]);\n\t\tlong include = curRide[1] - curRide[0] + curRide[2] + dp[nextAvailableRide];\n\t\tlong exclude = dp[idx + 1];\n\t\tdp[idx] = Math.max(include, exclude);\n\t}\n\treturn dp[0];\n}\n\nprivate int findNextAvailableRideBS(int[][] rides, int lo, int preEnd) {\n\tint hi = rides.length;\n\twhile (lo < hi) {\n\t\tint mid = lo + (hi - lo) / 2;\n\t\tif (rides[mid][0] < preEnd)\n\t\t\tlo = mid + 1;\n\t\telse\n\t\t\thi = mid;\n\t}\n\treturn lo;\n}\n```
['Dynamic Programming']