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?

CodePudding user response：

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);
}

CodePudding user response：

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;
}