Dynamic Programming Basics

This is very interesting programming / algorithm problem solving technique.
There is a lot of information on this from bing/google about theory and some examples.

What I would like to post is, working example code with some explanation.

Lets consider a simple problem:
Prob) Find the largest strictly increasing continuous sub-sequence from the given sequence.

e.g Seq: 4,5,1,6,3,6,7,9,2,4

Here as we see that increasing sub-sequences are:
1) 4,5
2) 1,6
3) 3,6,7,9
4) 2,4

Hence, the largest turns out to be 3)3,6,7,9
In brute-force / general logic, we would find a max length at each index.
e.g Start at 4, 4>5, max length at 4 is 1, proceed further, compare 4 with 1, 4>1, so the max length remains same(1) else increment it.

Here is C code for same:

int IncSeq::getLargestSeq1(string &seq)
{
    cout<< " Seq:"<<seq<<endl;
    int maxLen = seq.length();
    int i=0,j=0,cnt=0,s=0,max=0,len=0;
    for (i=0; i<maxLen; i++)
    {
        cnt = 0;
        s=i;
        for (j=i+1; j <maxLen-1; j++)
        {
            if ( seq[j] > seq[s] )
            {
                len = ++cnt;
                s++;
            }
            else
               break;
        }
        if (len>max)
            max = len;
    }
    return max;
}

The algorithm takes O(N²).
If we notice, the problem can be divided into sub-problems (on lines of dynamic programming) of find the increasing length from each of the index. At each index we compare the index element with next element and accordingly increment the number.
If we separate the inner loop as follows:

int IncSeq::increasingLenFromIndexM(int i, string &seq, int maxLen)
{
    if (maxLen == 0)
        return 0;

    if ( seq[i+1] > seq[i] )
        return 1+increasingLenFromIndexM(i+1, seq, maxLen);
    else
        return 0;
}

So we see here that if objective of seq[i+1]>seq[i] is satisfied, add to result the next sub-problems result. You can use it as:

int IncSeq::getLargestSeq1(string &seq)
{
    cout<< " Seq:"<<seq<<endl;
    int maxLen = seq.length();
    int i=0,max=0,len=0;

    for (i=0; i<maxLen; i++)
    {
        len = increasingLenFromIndexM(i, seq, maxLen);
        if (len>max)
            max = len;
    }

    return max;
}

Another property of dynamic programming is to memoise the answers to sub-problems so that we don't solve them again in recursion. The simplest is to save the answers in an array/table and check it at entry of every sub-problem as follows:

int IncSeq::increasingLenFromIndexM(int i,
string &seq, int maxLen)
{
    int res =0;
    if (maxLen == 0)
        return 0;

    if (ans[i]!=0)
        return ans[i];

    if ( seq[i+1] > seq[i] )
        res = 1+increasingLenFromIndexM(i+1, seq, maxLen);
    else
        res = 0;

    ans[i] = res;
    return res;
}

Now if you see, it boils down to filling the table with answers of sub-problems.
What if start filling the table backward ? , then we can completely skip memoising the answers.

void IncSeq::dFillAnswers(vector<int>& A, int N)
{
    ans[N]=0;

    for (int i=N-2; i>=0; i-=1)
    {
        if ( A[i] < A[i+1] )
            ans[i]=1+ans[i+1];
        else
            ans[i]=0;
    }
}

and in function "increasingLenFromIndexM" just return the ans[index].
Thus we have solved the problem using dynamic programming