"Dynamic Programming"

Written By Atticus Kuhn
Tags: "public", "project"
: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

See Also

Asymptotic Complexity of Computable Function

Leave your Feedback in the Comments Section