Tag Archives: optimization

A crack at Dynamic Programming

Dynamic Programming is a discrete optimization technique. It means, the variables we want to calculate using this method are discrete. As an example, if x is one such variable then x\in\{1,2,3,4\} is acceptable, but ‘x is a real number between 0 and 1′ is NOT acceptable since there are infinitely many real numbers between 0 and 1. In math terms, we can say that the domain of the variable x is a countable set.

Problems that are solved by dynamic programming are recursive nature. Let’s look at the problem that ask us to calculate the sum up to a number, i.e., if f_s is such a function then f_s(5)=0+1+2+3+4+5. The recursive definition (assuming i is non negative) is following:

f_{s}(i)=\begin{cases}0 & ,i=0\\i+f_{s}(i-1) & ,i\geq1\end{cases}
Continue reading