Dynamic Programming Part I - Introduction

All combinatoric problems can be solved by Brute-force search. But if search space is very large, Brute-force search required very much time and performance to search for solutions. However, we can reduce search space by input the constraints, which is Constraint Programming. And another optimization is to find the pattern of search space, it is Dynamic Programming.

Problems which can be solved by Dynamic Programming, must contains 2 properties, which are

- Optimal Substructure
- Overlapping Subproblems

Optimal Substructure means, the sub-function must return the same solution everytime. For instance,

Start is a problem. The problem can be splitted into 3 sub-problems. Straight lines are known costs. Wavy lines are optimal costs of the sub-problems. If optimal costs is able to determine, the optimal solutions is also able to determine. The minimum cost for this problem is 25 (5 + 20). But if the optimal solutions on wavy lines cannot be determined, then there is no optimal substructure.

Overlapping Subproblems means, the main function must be splitted into sub-function, and all sub-functions should share the same function. For instance, for a Fibonacci number, it is equal to the sum of 2 previous Fibonacci numbers. We can write into function: F(n) = F(n - 1) + F(n - 2). And we must also define the end point of recursive function: F(0) = 0, F(1) = 1.



Dynamic Programming in practical makes use of
- Recursion
- Pattern Matching
- Memoization

Recursion is function that can be splitted into sub-function of itself. In C#, it doesn't support anonymous recursive function, we have to set it to null before make the recursion.

Func<long, long> fibo = null;
fibo = n => fibo(n - 1) + fibo(n - 2);

Pattern Matching is to check the input parameter, and reroute to the the appropriate function. For me, I used When method, this method can be found in delegate article, part I, and part II.

fibo = fibo.When(n => n == 1, n => 1);
fibo = fibo.When(n => n == 0, n => 0);

Memoization is technique to cache the result to speed up calculation. Because dynamic programming is optimal substructure, the sub-function can be determined. Memoization is very important to make dynamic programming processes faster. (Memoize method also can be found in delegate article, part I, and part II)

fibo = fibo.Memoize();

Now we can combine it all together.

Func<long, long> fibo = null;
fibo = n => fibo(n - 1) + fibo(n - 2);
fibo = fibo.When(n => n == 1, n => 1);
fibo = fibo.When(n => n == 0, n => 0);
fibo = fibo.Memoize();

Dynamic programming is now completed for Fibonacci function. To call function, is very simple.

Console.WriteLine(fibo(38));
//39088169

Next article, some more examples on dynamic programming.