Given N tasks in a game which need to be performed in any order. Initially, we have a power of 1 unit and speed of 1 unit. The $$$i^{th}$$$ task requires a minimum of $$$A_{i}$$$ power or $$$B_{i}$$$ speed. On completing the ith task we get $$$C_{i}$$$ points which can be used to increase speed or power. 1 point can be used to increase 1 power or 1 speed. Find the maximum number of tasks that can be completed.
1<=N<=100
1<=A[i],B[i],C[i]<=1000
Example:
Input:
A=[1,1,2,7]
B=[1,3,4,4]
C=[2,3,1,1]
Output: 4
Looking at the contraints and nature of the problem, it seems that dynamic programming can easily solve this problem and would be best solution. Since everything depends upon the order of choosing i, therefore at each i you can try out remaining n-1 values to go on ( probably recursively build up ). After writing recursive you can identify the required states most probably (i,j) where you choose to go from i to j but at the same time we also need to see at what point or at what step did we jump from i to j, so another parameter k would come into play denoting the step at which you are jumping, so dp states could be (i,j,k) denoting jumping from i to j task at kth step. This would give you a dp of i*j*k whose max values are all upto 100, so 10^6 max which can easily pass, so O(N^3) dp solution can work.
How would we keep track of which tasks are done so that we don't do the same task more than once ?
Can you prove that this problem is not from an ongoing contest (e.g. by sharing a link)?