want to solve algorithm problem using dynamic programming

  algorithm, c++, dynamic-programming, matrix

The problem is minimal cost path in matrix, and dynamic programming is required.

Path movements can be moved left, bottom, and left bottom diagonally.

Starting from row 1, column n, go to row n, column 1. ex is

4 5 3

2 3 6

4 7 5

then start row 1, column 3 the value is 3 and the end is row 3, column 1 the value is 4, and the minimum cost is 10 go to 3 -> 3 -> 4

I want to solve using dyanamic programming but can’t well

occur the wrong and segmentation fault

Please let me know

Thank you

Here’s my code

#include <vector>
#include <bits/stdc++.h>
#include <limits.h>

#define MAX 1000
int cost[MAX][MAX];
int M[MAX][MAX];

using namespace std;

int min(int x, int y, int z)
{
   if (x < y)
      return (x < z)? x : z;
   else
      return (y < z)? y : z;
}

int minCost(int n)
{   
    int j;
    j= n - 1;
    
    for (int i= 1 ; i<n ; i++){ // first row
        cost[i][0] += M[i-1][0];
    }
 
    while(j != 1){              // end column
        cost[0][j] += M[0][j+1];
        j--;
    }
    j= n - 1;
    
    for (int i=1 ; i<n ; i++) { // rest 2d matrix
        while(j != 1){
            cost[i][j] += min(M[i-1][j+1], M[i-1][j], M[i][j+1]);
            j--;
        }
    }
 
    return cost[n-1][1];
}

int main(){
    int n;  //matrix size
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d",&M[i][j]); // input 2d matrix
        }
    }
    
    cout << minCost(n) << endl;  // print the minimum cost

    return 0;
}

Source: Windows Questions C++

LEAVE A COMMENT