Calculate maximum path cost for a matrix in C

Question

I am learning c and encountered maximum cost path question in which

Rules:

1. matrix is n x n size

2. Starting from the cell (bottommost leftmost cell), you want to go to the topmost rightmost cell in a sequence of steps. In each step, you can go either right or up from your current location.

I tried to solve using dynamic programming and this is the function I have written

computecost(int *utr,int n)//utr is the input matrix 
{
 int *str;
 int i,j;
 str=(int *)malloc(n*n*sizeof(int));
 for(j=0;j<n;j++)//intialization of bottom row
 {
      str[n*(n-1)+j]=utr[n*(n-1)+j];
 }
 for(i=n-2;i>=0;i--)
 {
     for(j=0;j<n;j++)
     {
         str[n*i+j]=utr[n*i+j]+max(str[n*(i+1)+j],str[n*(i+1)+(j+1)]);   
     }
 }
 
printf("%d",str[n*0+0]);
 
 return 0;
}

and this is the input

for(i=0;i<n;i++)
 {
     for(j=0;j<n;j++)
     {
         scanf("%d",&str[n*i+j]);
     }
 }  

but for the matrix 5 x5

1   4   8   2   9 

32  67  18  42  1 

4   86  12  7   1 

8   4   12  17  44

1   43  11  45  2 

the desired output is 272 but I am getting 211.

the output matrix for my case

  1   43  11  45  2
  51  47  57  62  46
  55  143  74  69  47
  175  210  92  111  52
  211  214  119  113  64

Can anyone help me?

Answer 1

You don't need dynamic programming for this since there are no overlapping sub-problems. Just use a simple recursion.

const int n = 5;
int mat[n][n] = {
    {1,4,8,2,9},
    {32,67,18,42,1},
    {4,86,12,7,1},
    {8,4,12,17,44},
    {1,43,11,45,2}
}; // input matrix

int f(int x, int y, int sum){
    if(x == 0 && y == 4)
        return sum;

    int p = 0, q = 0;
    if(x - 1 >= 0)
        p = f(x-1, y, sum + mat[x-1][y]);
    if(y + 1 <= 4)
        q = f(x, y+1, sum+mat[x][y+1]);
    return max(p,q);
}

int main(){
    int maxSum = f(4,0, mat[4][0]);
    printf("%d\n", maxSum);
}

Answer 2

You were not very far to succeed.
In practice, you did not initialize correctly the bottom row.
Moreover, there was a little mistake in the iteration calculation.

This is the corrected code.
As said in a comment, it could be further simplified, by avoiding the use of a new array, simply updating the input array.

#include <stdio.h>
#include <stdlib.h>

int max (int a, int b) {
    return (a > b) ? a : b;
}

int computecost(int *utr,int n) {   //utr is the input matrix 
    int *str;
    str = malloc (n*n*sizeof(int));
    str[n*n - 1] = utr[n*n - 1];
    for (int j = n-2; j >= 0; j--) {    //intialization of bottom row {
        str[n*(n-1)+j] = utr[n*(n-1)+j] + str[n*(n-1)+j+1];       // corrected
    }
    for (int i=n-2; i>=0; i--) {
        str[n*i+n-1] = utr[n*i+n-1] + str[n*(i+1)+n-1];
        for(int j = n-2; j >= 0; j--) {
           str[n*i+j] = utr[n*i+j] + max(str[n*(i+1)+j],str[n*i + j+1]); // corrected
        }
    }
    int cost = str[0];
    free (str);
    return cost;
}

int main() {
    int A[25] = {
        1,43,11,45,2,
        8,4,12,17,44,
        4,86,12,7,1,
        32,67,18,42,1,
        1,4,8,2,9
    };
    int ans = computecost (A, 5);
    printf ("%d\n", ans);
    return 0;
}