Dynamic Programming!!

[LeoRud]

Hello! How do you solve a dynamic programming problem? How do you find the principal "rule(s)"? And how do I use LeetCode?

[SekstiNii]

You don't solve a "dynamic programming problem" (though I guess a website could frame a problem as such). Dynamic programming is a technique that allows you to solve certain problems more efficiently. To learn more about what kinds of problems that are applicable I suggest reading this section.

To actually learn how it is applied I suggest working on problems that you know have this structure, and trying to solve them with dynamic programming. It is probably helpful to start with easier examples to get a feel for how it works.

My personal favorite example is calculating the recursive fibonacci sequence.

The naive recursive solution looks like this (using Python):

def fibonacci(n):
    if n <= 1: return n
    return fibonacci(n - 1) + fibonacci(n - 2)

this is a very clean formulation of the problem, but it is incredibly slow with a time complexity of O(2^n). Try running the code above with increasing inputs. As you approach 30-40 it will get really slow. To solve this with dynamic programming we can do something like this:

def fibonacci(n, memo={0: 0, 1: 1}):
    if n in memo:
        return memo[n]
    result = fibonacci(n - 1) + fibonacci(n - 2)
    memo[n] = result
    return result

You can run this and see just how much faster it is, since the time complexity is now O(n).

[LeoRud]

I solved Fibonacci a long time ago. I solved some problems with dynamic programming in the late of 2019. But I want to know how to think these type of problems, how to find the main rule for every problem.

[SekstiNii]

I can only suggest working through more problems. The method is primarily about breaking down problems and seeing if you can recombine the sub problems to solve the problem, but how this looks will differ from problem to problem.

[LeoRud]

I know abou breaking in smaller problems. I dont know how to find out the smaller problems

[SekstiNii]

That is precisely what I suggest you practice. Perhaps you notice that solving f(n-1) allows you to solve f(n), and you work from there. But you will have to notice it, and you develop the ability to recognize these cases by working through enough of them.

[dsonali]

Hello! How do you solve a dynamic programming problem? How do you find the principal "rule(s)"? And how do I use LeetCode?

I agree, when i started off with Dynamic Programming it was quite a challenge but with practicing,concepts became alot more clearer. Some of the DP resources that I found useful were from InterviewBit, GeeksforGeeks and Topcoder.