Trying to understand this dynamic programming python code?

dynamic programming python example
dynamic programming in python pdf
dynamic programming problems and solutions
dynamic programming python book
dynamic programming explained
dynamic programming geeksforgeeks
dynamic programming table method
elements of dynamic programming

So I am reading this excellent intro to Dynamic Programming, and I am trying to decipher this python code (DP approach for Fibonacci numbers). I code mainly in C/C#, so its kinda hard for me to understand Python. So this is the code:

def fibonacciVal(n):
    memo = [0] * (n+1)
    memo[0], memo[1] = 0, 1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n]

So, the bits I am trying to understand are:

  1. memo = [0] * (n+1) : I get that this is an array, but how are the values being stored here, how is it being initialized?

  2. for i in range(2, n+1): : why is it looping till n+1, shouldn't it be till n only?

That's all. I am trying to decipher this myself, and it would help to have someone with python experience help me here.

Thanks!

memo = [0] * (n+1) : I get that this is an array, but how are the values being stored here, how is it being initialized?

When you multiply a one-element list by an integer in Python, it initializes a list with that one element repeated however many times you specified. For example, for n=5:

memo = [0] * (n+1)

will initialize a list of 6 0s and assign it to the variable memo.

>>> n = 5
>>> memo = [0] * (n+1)
>>> memo
[0, 0, 0, 0, 0, 0]

Be aware that this method for initializing lists works fine for lists of immutable objects (booleans, numbers, strings, etc.), but doesn't work very well for mutable objects (like lists of lists, or lists of dictionaries). This is because Python adds n copies of the same object to the list, which is not normally what you'd want. (When you try to change one of the mutable objects in your lists, all of them will change, since they're all just copies of the same object.)


for i in range(2, n+1): : why is it looping till n+1, shouldn't it be till n only?

It does stop at n, since that's the built-in behavior of the range function. When you pass in two arguments, they are its start and stop values. The range function will return the sequence from start (inclusive) to stop (exclusive).

If instead you said range(2, n), it would stop at n-1. (Another way to think about it is, adding 1 to n is what makes it stop at n.)

Trying to understand this dynamic programming python code , memo = [0] * (n+1) : I get that this is an array, but how are the values being stored here, how is it being initialized? When you multiply a  Fibonacci series in python using recursion and dynamic programming with code explanation Please try again later. Program to check prime number with code in python optimized

1: [0]*3 -> [0,0,0] i.e. multiplying an array duplicates it that many times -n+1 in your case-.
2: because you start with [0,1,0,0,0, ...]
 the first index you add to is ^

... the last index you add to will be at n+1 because the first index you added to was 2
[0,1,1,2,3,5,8,13,21,...]

Solving Problems With Dynamic Programming, Dynamic programming is a really useful general technique for solving problems that involves breaking The code is written in basic python with no special dependencies. Let's try it out on a pretty small number first. has made me a better engineer, and that in of itself makes it worth the time investment to understand. Below is some Python code to calculate the Fibonacci sequence using Dynamic Programming. def fibonacciVal(n): memo[0], memo[1] = 0, 1 for i in range(2, n+1): memo[i] = memo[i-1] + memo[i-2] return memo[n]

What tools are you using for "trying to understand"? A couple of basic print commands will help a lot:

def fibonacciVal(n):
    memo = [0] * (n+1)
    print("INIT", memo)
    memo[0], memo[1] = 0, 1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
        print("TRACE", i, memo)
    return memo[n]

fibonacciVal(5)

Output:

INIT [0, 0, 0, 0, 0, 0]
TRACE 2 [0, 1, 1, 0, 0, 0]
TRACE 3 [0, 1, 1, 2, 0, 0]
TRACE 4 [0, 1, 1, 2, 3, 0]
TRACE 5 [0, 1, 1, 2, 3, 5]

Demystifying Dynamic Programming, Maybe you're trying to learn how to code on your own, and were told Using dynamic programming (DP) to write algorithms is as essential as it is feared. opt for a recursive algorithm that looks something like this in Python: Programming languages: Python and Java VS Code extensions get these new updates. Java for Visual Studio Code now gets SonarLint 'spellchecker' tool, while the Python extension gets a new debugger.

Follow these steps to solve any Dynamic Programming interview , 7 Steps to solve a Dynamic Programming problem In this problem, we're on a crazy jumping ball, trying to stop, while us strengthen the understanding of the recurrence relation from step 1. Here is python code for that: The Dynamic Programming is a cool area with an even cooler name. It shows how Reinforcement Learning would look if we had superpowers like unlimited computing power and full understanding of each

Python, In order to understand the implementation of the dynamic programming in python​, lets visualize it using the Fibonacci Python program to find the nth Fibonacci. No problem: You can go ahead and read the code. While dipping into external code libraries takes a bit of coding maturity, it’s very useful for. helping you understand the details of a particular implementation, and; building your programming skills by showing you code written by first-rate programmers.

How to solve a Dynamic Programming Problem ?, Dynamic Programming (DP) is a technique that solves some particular type of Before we study how to think Dynamically for a problem, we need to learn: The above code seems exponential as it is calculating the same state again and again. One must try solving various classic DP problems that can be found here. There are parallels to this question: Can I avoid Python loop overhead on dynamic programming with numpy? I'm happy to switch to C if necessary, but I like the flexibility of Python for rapid testing and the lack of faff with file IO. Off the top of my head, is something like the following code likely to be significantly faster?

Comments
  • It's a memoized version of fibonacci so it doesn't recompute already computed values.
  • The second arg in this use of range() is when to stop.
  • Before you try to understand dynamic programming you need to understand the tools with which it's implemented. Please look up the Python basics before posting here: initializing a list and the range iterator.
  • You could have figured all of this out in 10 minutes by reading the docs, 5 minutes by stepping through in a debugger, or 60 seconds by playing around with the repl. If you didn't know about any of those, well then ok, but now you know for next time.
  • The memo initialization can be shortened to memo = [0, 1] + [0] * (n-2)
  • Thank you ! This helped me understand Python a bit better :)
  • I just explored the code mhyself, before reading the answers, and I did have it figured out. Reading your answer made my understanding more solidified. Thank you!
  • Yeah, print is the way to go when trying to understand something. Also, I was not aware of python having INIT and TRACE parameters for the print(). Thank you, you have enriched my knowledge!
  • Those are not parameters: they're merely text labels I use to differentiate the output.