Minimum Number of Days to Eat N Oranges - Dynamic Programming - Leetcode 1553 - Python

0:00 - Read the problem
2:33 - Drawing Explanation
13:58 - Coding Explanation

leetcode 1553

#dynamic #programming #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[deathbombs]

each day has 3 actions that depend on n oranges remaining. DP is suitable here with top down or bottom up

Bottom up building output:
dp[n] = maximum number for n oranges remaining

dp[0] = 0
dp[1]=1
dp[2] = Math.min(dp[2-1]+1, dp[2/2] +1) = 2
dp[3] = math.min(dp[3-1]+1, dp[2*3/3]+1
...

Top down:
CalculateTopDown(int n, int[] dp )
{
if(n <= 1) return n;
BestResult = CalculateTopDown(n-1)+1
if(n%2==0)
BestResult = Math.min(bestResult, calculateTopDown(n/2)+1);


if(n%3==0)
BestResult = Math.min(bestResult, 2*calculateTopDown(n/3)+1);

dp[n] = bestResult

reutnr bestResult
}

[nivethagovindan]

Your DP videos are awesome keep posting!!!

[algorithmo]

@NeetCode I think you made a mistake at 13:20, it should be 1 + 3 + 1 = 5 instead of 1 + 2 + 1. I think you missed the n/3

[sabaamanollahi]

Thanks NeetCode, so isn't it a branch and bound method?

[Utkarshgg]

The only solution on the internet that explains this peoblem...others are just copying hints

[mik]

the agreement on leetcode is that time complexity is O(log^2(N), ) not O(log(N)).

[sudhanshuverma]

Awesome explanation. You made it look easy.

[ireacttoshit]

you said bfs but wrote a dfs function, I'm confused

[CS_nb]

I don't really get why we have to write return dp[n] for the second time

[rahulchatterjee]

Incorrect thumbnail, it's 1553 not 1533 :)

[Anveshana]

Hey @NeetCode, can you also convince us why greedy works ?

[jonaskhanwald]

You made it to look like a easy problem

[aadil]

I have a question? in the description it says we have to multiply it by 2 after dividing it by 3. And We're only dividing it by 3. This is the only thing that confuses me. Can anyone help? please

[algorithmo]

@NeetCode next is binary tree cameras please!! Dynamic programming problem too!

[poptart-br]

you really churned those dp problems last june :d