91Ó°ÊÓ

Dynamic programming is a paradigm used for writing algorithm which helps to solve some particular type of problems more efficiently by saving the solution of subproblems and using them to get the final solution. Rather than performing the same calculation again and again, the optimal solution to subproblems are calculated and stored.

Consider$D\left(u\right)$ as sub-problem such that $u=\left\{1,….,v\right\}$.

Thus, according to question,$D\left(u\right)$ is true if it is possible to make change for v using coins denomination.$x_1,x_2,…x_n$

$D\left(u\right)=\left\{\begin{array}{c}TRUE;\text{ifitispossibletomakechangefor}v\\ \text{FALSE};\text{otherwise}\end{array}\right.$

Now, taking$D\left(u\right)$ as sub-problem, if it is possible to make change for$v$ using denomination,$x_1,x_2,…x_n$then it is also possible to make change for by using same denomination with the coin.

The desired recursion is:

Here, ‘’ is the value for which we finding denomination.