[algogeeks] Re: Minimal path sum in a matrix (optimizing the algorithm)

[Karthik Krishnamurthy]

Hi,
I think DP(Dynamic Programming) will help you better than memoization because in the case of DP there isn't any recursive calls.
As for as your problem is concerned, DP will run in O(n^2). The solution is pretty simple.

The first thing that must be observed is that there are at most 2 ways we can come to a cell - from the left (if it's not situated on the first column) and from the top (if it's not situated on the most upper row). Thus to find the best solution for that cell, we have to have already found the best solutions for all of the cells from which we can arrive to the current cell.

>From above, a recurrent relation can be easily obtained:
>> For the first row, simply calculate S[i][j]=S[i][j]+S[i][j-1];
>> For the first col, simply calculate S[i][j] =S[i][j]+S[i-1][j];
>> For the rest of the matrix, calculate S[i][j] = max(S[i][j]+S[i-1][j], S[i][j]+S[i][j-1]);

Your final answer will be stored in the location S[N-1][N-1];

The code will be -
int main() {
    int a[80][80];
    int N;
    //Read the values;
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            if(i>0 && j>0)
                a[i][j] = min(a[i][j]+a[i-1][j],a[i][j]+a[i][j-1]);
            else if(i==0 && j>0)
                a[i][j]=a[i][j-1]+a[i][j];
            else if(j==0 && i>0)
                a[i][j]=a[i-1][j]+a[i][j];
        }
    }
    cout<< a[N-1][N-1];
}

To know more about DP check this site - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
For other algorithmic tutorials - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index


--~--~---------~--~----~------------~-------~--~----~
 You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---