what is Dynamic Programming

what is Dynamic Programming

  2월 18, 2022    Eunhan's library

---

Dynamic Programming

Definition

One of problem solving technique

Split huge problem into many simple subproblems and reduce steps of subproblems.
Then get solution by addition of all subproblems.

Example

if you calculate $2^1+2^2+2^3+2^4+2^5$,

You can find answer by calculating
$2+(2*2)+(2*2*2)+(2*2*2*2)+(2*2*2*2*2)$

However, there is another way in computer.
$2^1=2=2$
$2^2=2*2=2^1*2$
$2^3=2*2*2=2^2*2$
$2^4=2*2*2*2=2^3*2$
$2^5=2*2*2*2*2=2^4*2$

You can skip some of parts that you already calculated. When you calculate the $2^5$, you done have to calculate $2^4$ if that number $2^4$ is already calculated.