What is DP
Dynamic programming is a programming paradigm for a massive class of problems. It solves the problem by partitioning it into smaller subproblems and solving it to avoid double computing the same results. Thus, the optimal solution of the main problem depends on the optimal solution of its subproblems.
The simplest (even classic) example is solving the Fibonacci Numbers problem - find the n-th Fibonacci number. As you know, each next Fibonacci number is a sum of the previous two Fibonacci numbers. So, if we have some function fib(n) that returns n-th Fibonacci numbers, we can implement it like this:
12def fib(n): return fib(n-1) + fib(n-2)
Thus, to solve the problem of the n-th Fibonacci number, you should solve the fib(n-1) and fib(n-2) subproblems first. But we can solve both of these subproblems in the same way.
You can note that this recursion has no bottom yet, so we have to add the stop condition:
1234def fib(n): if n <= 1: # Bottom return n return fib(n-1) + fib(n-2)
You'll find some info about the main DP properties in the next two chapters.
Swipe to start coding
- Following the example, implement the function
fib(n). - Make function calls to check how it works.
The function calls are already in the task code; do not change them. Edit the fib(n) function only.
Lösning
Tack för dina kommentarer!
single
Fråga AI
Fråga AI
Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal
Sammanfatta detta kapitel
Explain code
Explain why doesn't solve task
Awesome!
Completion rate improved to 8.33What is DP
Svep för att visa menyn
Dynamic programming is a programming paradigm for a massive class of problems. It solves the problem by partitioning it into smaller subproblems and solving it to avoid double computing the same results. Thus, the optimal solution of the main problem depends on the optimal solution of its subproblems.
The simplest (even classic) example is solving the Fibonacci Numbers problem - find the n-th Fibonacci number. As you know, each next Fibonacci number is a sum of the previous two Fibonacci numbers. So, if we have some function fib(n) that returns n-th Fibonacci numbers, we can implement it like this:
12def fib(n): return fib(n-1) + fib(n-2)
Thus, to solve the problem of the n-th Fibonacci number, you should solve the fib(n-1) and fib(n-2) subproblems first. But we can solve both of these subproblems in the same way.
You can note that this recursion has no bottom yet, so we have to add the stop condition:
1234def fib(n): if n <= 1: # Bottom return n return fib(n-1) + fib(n-2)
You'll find some info about the main DP properties in the next two chapters.
Swipe to start coding
- Following the example, implement the function
fib(n). - Make function calls to check how it works.
The function calls are already in the task code; do not change them. Edit the fib(n) function only.
Lösning
Byt till skrivbordet för praktisk övningFortsätt där du är med ett av alternativen nedanTack för dina kommentarer!
Awesome!
Completion rate improved to 8.33single
