Please cover this question in one of your videos https://leetcode.com/problems/maximize-the-profit-as-the-salesman/ #16
Description
The recursive code I wrote obviously gave TLE but worked
class Solution
{
int[] dp;
public int solve(List<List<Integer>> arr, int prev_start, int prev_end, int i)
{
if(i == arr.size())
return 0;
List<Integer> cur = arr.get(i);
int start = cur.get(0);
int end = cur.get(1);
int taken = 0;
if(start > prev_end)
taken = cur.get(2) + solve(arr, start, end, i+1);
int not_taken = solve(arr, prev_start, prev_end, i+1);
return Math.max(taken, not_taken);
}
public int maximizeTheProfit(int n, List<List<Integer>> arr)
{
Collections.sort(arr, (a, b) -> a.get(1) - b.get(1));
dp = new int[n];
Arrays.fill(dp, -1);
return solve(arr, -1, -1, 0);
}
}The dp I tried to make from this did not work, if you could help me figure out why, I'll be grateful :)
class Solution
{
int[] dp;
public int solve(List<List<Integer>> arr, int prev_start, int prev_end, int i)
{
if(i == arr.size())
return 0;
List<Integer> cur = arr.get(i);
int start = cur.get(0);
int end = cur.get(1);
int taken = 0;
if(cur.get(2) < dp[end])
{
return dp[end];
}
if(start > prev_end)
taken = cur.get(2) + solve(arr, start, end, i+1);
int not_taken = solve(arr, prev_start, prev_end, i+1);
return dp[end] = Math.max(taken, not_taken);
}
public int maximizeTheProfit(int n, List<List<Integer>> arr)
{
Collections.sort(arr, (a, b) -> a.get(1) - b.get(1));
dp = new int[n];
Arrays.fill(dp, -1);
return solve(arr, 0, 0, 0);
}
}