You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/dynamic_programming/intro-to-dp.md
+3-3Lines changed: 3 additions & 3 deletions
Original file line number
Diff line number
Diff line change
@@ -7,7 +7,7 @@ tags:
7
7
8
8
The essence of dynamic programming is to avoid repeated calculation. Often, dynamic programming problems are naturally solvable by recursion. In such cases, it's easiest to write the recursive solution, then save repeated states in a lookup table. This process is known as top-down dynamic programming with memoization. That's read "memoization" (like we are writing in a memo pad) not memorization.
9
9
10
-
One of the most basic, classic examples of this process is the fibonacci sequence.It's recursive formulation is $f(n) = f(n-1) + f(n-2)$ where $n \ge 2$ and $f(0)=0$ and $f(1)=1$. In C++, this would be expressed as:
10
+
One of the most basic, classic examples of this process is the fibonacci sequence.Its recursive formulation is $f(n) = f(n-1) + f(n-2)$ where $n \ge 2$ and $f(0)=0$ and $f(1)=1$. In C++, this would be expressed as:
11
11
12
12
```cpp
13
13
intf(int n) {
@@ -25,7 +25,7 @@ Our recursive function currently solves fibonacci in exponential time. This mean
25
25
26
26
To increase the speed, we recognize that the number of subproblems is only $O(n)$. That is, in order to calculate $f(n)$ we only need to know $f(n-1),f(n-2), \dots ,f(0)$. Therefore, instead of recalculating these subproblems, we solve them once and then save the result in a lookup table. Subsequent calls will use this lookup table and immediately return a result, thus eliminating exponential work!
27
27
28
-
Each recursive call will check against a lookup table to see if the value has been calculated. This is done in $O(1)$ time. If we have previouslycalcuated it, return the result, otherwise, we calculate the function normally. The overall runtime is $O(n)$. This is an enormous improvement over our previous exponential time algorithm!
28
+
Each recursive call will check against a lookup table to see if the value has been calculated. This is done in $O(1)$ time. If we have previouslycalculated it, return the result, otherwise, we calculate the function normally. The overall runtime is $O(n)$. This is an enormous improvement over our previous exponential time algorithm!
29
29
30
30
```cpp
31
31
const int MAXN = 100;
@@ -88,7 +88,7 @@ This approach is called top-down, as we can call the function with a query value
88
88
Until now you've only seen top-down dynamic programming with memoization. However, we can also solve problems with bottom-up dynamic programming.
89
89
Bottom-up is exactly the opposite of top-down, you start at the bottom (base cases of the recursion), and extend it to more and more values.
90
90
91
-
To create a bottom-up approach for fibonacci numbers, weinitilize the base cases in an array. Then, we simply use the recursive definition on array:
91
+
To create a bottom-up approach for fibonacci numbers, weinitialize the base cases in an array. Then, we simply use the recursive definition on array: