:PROPERTIES:
:ID: f809e54d-6098-42bc-be33-10a2eb983cc1
:mtime: 20231012072648
:ctime: 20231012072531
:END:
#+title: Dynamic Programming
#+filetags: :public:project:
* Definition
Dynamic Programming is a technique in programming where we memoize and cache previous
results to speed up computations.
* Usage in Competative Programming
Dynamic programming is typically used in competative programming competitions to speed up solutions.
* Example of Dynamic Programming: Coin Box Problem
Here is an example of a problem which uses dynamic programming.
This problem is called the "money box problem".
** Problem Statement
You are given some boxes of money and a target amount.
Your goal is to choose some of the boxes to reach the target amount
using the fewest number of boxes.
You cannot choose a box multiple times
You cannot go over the target amount
** Example
Given the boxes 10,1,2,9,15,9 and the target 28,
you should return 10,9,9 because 10+9+9 = 28.
** Non-Dynamic Solution
Here is a non-dynamic solution:
induct on boxes. If there are 0 boxes, only 0 is reachable.
If there is a box $n$ and the rest of the boxes are $ns$,
check if $a-n$ is reachable with $ns$.
The [[id:43dd8110-2e8e-42a3-8d7a-55da895da68a][Asymptotic Complexity of Computable Function]] is
$O(2^n * n)$.
** Dynamic Programming Solution to the Problem
Have a table where you memoize the previous results.
Build up the solution from the smallest case.
* Example of Dynamic Programming: Money Pyramid Problem
** Naive Solution
#+BEGIN_SRC javascript
const moneyPyramidPos = (pyramid, position) =>{
if(pyramid.length === 1){
return pyramid[0][position];
}
if(position === pyramid[0].length - 1 ){
return pyramid[0][position] + moneyPyramidPos(pyramid.slice(1), position - 1);
}else{
return pyramid[0][position] + Math.max(moneyPyramidPos(pyramid.slice(1) , position), moneyPyramidPos(pyramid.slice(1), position - 1))
}
}
const moneyPyramid = (pyramid)=>{
};
#+END_SRC