Dynamic Programming Introduction

Going over the very basics of dynamic programming before we continue the series in more depth.

[bashmohandes]

The solution at 3:28 is actually the most optimal, it is in order of O(n) time and O(1) space.

[simranjeetsingh]

Nice video but there are certain errors:
1. You have labelled the iterative DP approach as 'top-down' approach but it actually is 'bottom-up' approach. Moreover, the
running time will be O(n) and space complexity will also be O(n).
2. The recursive approach is 'top-down' DP.

[sarasaeed]

Thanks for the video! I just can't understand how X1, X2, and X3 are taking O(n) space! shoudn't it be O(1)?

[kyryloreznykov]

Video with mistake about running time of simple loop. Bad example! What is the sense in recursion if it takes more memory? If you need memorize data, you can do it in a loop to!

[alexanderkuptsov]

Why do you need recursion while using a 'dictionary'? And calling it a dict is totally confusing as it looks more like an array to me.

[animatorFan]

This is thanks for making this vid and others like it :)

[jugsma]

Space can be made optimal by creating two temporary variables storing only two previous variables and swapping every time new value comes in. But, this implementation is still O(n).

[shahardagan]

private static long [] fib;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
fib = new long[n];
fib[0] = 0;
fib[1] = 1;


}


private static long FibList(int n) {
if (n <= 1) {
return 1;
} else {
if (fib[n] == 0)
fib[n] = FibList(n-1) + FibList(n-2);
return fib[n];
}
}
why it give me an error array index out of bound?

[nabajyotidash]

The 1st solution is more optimal than the second one having Time complexity of O(n) and space complexity of O(1)

[rajeshdansena]

@CSBreakdown I appreciate you corrected! But you must correct it more that the first approach is optimal. Take my words as feedback (positively) : Please do some research before making video and review your videos after making it. There are many people following you here and may blindly follow you, which is not good. I hope this helps. Keep up the good work. Thanks!

[debabhishek]

while(true){
System.out.println("like it" );
}

[MrVankog]

So you to answer the question why I came here.
What is dynamic programming?
Answer: *Recursion + Caching = dynamic programming*

[PROcrastiDRIVESVofficial]

It's ridiculous how we have to know this at uni, but in reality it is completely impractical and unnecessary.

[jhonnyappleseed]

This video is wrong for so many reasons:
- The 'run time of Fibonacci' is not defined, because it depends on implementation. You chose to use the recursive solution. That is why your default is O(2^n)
- The run time of the iterative method is O(n), not Omega(n^2), whatever that means
- You are demonstrating memoization, not dynamic programming
- Your memoization solution is no more 'bottom up' than the default recursive solution (which is 'bottom up' for the same reason - you recurse to your base case and then build up)
- Finally, in reality dynamic programming is just an interview exercise. It is never, ever used by any practicing programmer, just like no practicing programmer has ever had to compute the Fibonacci sequence, write a factorial function, divide without division, or any of the other nonsense we're asked in interviews. But that makes your confident ignorance even more tragic because people seeking to pass interviews will listen to your errant nonsense and fail.

[NoahWillCrow]

This video is so wrong and so misleading...

[rj-njuk]

Will you sir, please marry me, if you aren't married yet?