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 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 is such a function then . The recursive definition (assuming i is non negative) is following: