Максимальная сумма пути в 2d матрице

Question

Мне нужно найти максимальную сумму пути сверху вниз, пока я не достигну последней строки матрицы.

Мне нужно использовать рекурсивную функцию, которая возвращает максимальную сумму.Спускаясь вниз, мы можем двигаться только на один ряд вниз и на один столбец вправо, влево или прямо вниз.Мой код только возвращает первый индекс матрицы.Правильна ли моя логика, а также параметры, которые я использовал для своей функции?

    int mat[3][3], i, j;

    printf("Enter the elements of the matrix :\n");

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

    printf("%d", MaximumPath(mat, 0, 0));
}

int MaximumPath(int Mat[][N], int i, int j) {
    // IF we reached to first row of 
    // matrix then return value of that 
    // element  
    if (i == 0 && j = 0)
        return Mat[i][j]

    // out of matrix bound 
    if (i = N || j < 0)
        return 0;

    // call all rest position that we reached
    // from current position and find maximum 
    // between them and add current value in 
    // that path 
    return max(MaximumPath(Mat, i - 1, j), 
               MaximumPath(Mat, i - 1, j - 1), 
               MaximumPath(Mat, i - 1, j + 1)))
               + Mat[i][j];
}

int max(int i, int j, int k) {
    if ((i > j) && (i > k)) {
        return i;
    } else
    if ((j > i) && (j > k)) {
        return j;
    } else
    if ((k > i) && (k > j)) {
        return k;
    }
}

Answer 1

Я вижу несколько небольших проблем в вашем коде, даже если во всем мире идея о том, как найти путь максимального значения, уважается и понимается.
Если я правильно понял ваши объяснения, есть три возможных шага: вниз, вниз и влево, вниз и вправо. Что дает более или менее этот код:

int MaximumPath(int Mat[][N], int i, int j){
    // reached last row -> final case
    if (i == N-1){
            return Mat[i][j];
    }
    int max_value = MaximumPath(Mat, i+1, j);
    int tmp;
    if (j > 0){
        tmp = MaximumPath(Mat, i+1, j-1);
        if (tmp > max_value){
            max_value = tmp;
        }
    }
    if (j < N-1){
        tmp = MaximumPath(Mat, i+1, j+1);
        if (tmp > max_value){
            max_value = tmp;
        }
    }
    return max_value + Mat[i][j];
}

Answer 2

В вашем коде несколько проблем:

• В if (i == 0 && j = 0) есть синтаксическая ошибка: она должна быть j == 0, но нет причин возвращаться, когда вы находитесь в верхнем левом углу, это то место, с которого вы начинаете!
• Отсутствует ; в конце return Mat[i][j]
• В конце MaximumPath(Mat, i - 1, j + 1)))
• Вы должны передать i + 1 своим рекурсивным вызовам на MaximumPath, а не i - 1.

• Вы должны проверить, находится ли j внутри границ матрицы и вернуть 0, если нет, и исправить тест if (i = N || j < 0) как

  if (i >= N || j < 0 || J >= N)
  

• Функция max также неверна: она не возвращает значение, если 2 значения равны и больше, чем третье.

• вам, вероятно, следует попробовать другие начальные точки, такие как (0, 1) и (0, 2). В противном случае, это не соответствует вводимым значениям для этих ячеек, а также для ячейки (1, 2).

Вот исправленная версия:

#include <stdio.h>

#define N 3

int MaximumPath(int Mat[][N], int i, int j);

int main() {
    int mat[N][N], i, j;
    int max;

    printf("Enter the elements of the matrix :\n");

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            if (scanf("%d", &mat[i][j]) != 1)
                return 1;
        }
    }
    max = 0;
    for (j = 0; j < N; j++) {
        max = max3(max, max, MaximumPath(mat, 0, j));
    }
    printf("%d\n", max);
    return 0;
}

int max3(int i, int j, int k) {
    if (i >= j && i >= k) {
        return i;
    } else
    if (j >= i && j >= k) {
        return j;
    } else {
        return k;
    }
}

int MaximumPath(int Mat[][N], int i, int j) {
    // out of matrix boundaries
    if (i >= N || j < 0 || j >= N)
        return 0;

    // compute the maximum path from the current cell
    // for all possible directions:
    return max3(MaximumPath(Mat, i + 1, j - 1), 
                MaximumPath(Mat, i + 1, j), 
                MaximumPath(Mat, i + 1, j + 1)) + Mat[i][j];
}

Обратите внимание, что было бы более эффективно проверить границы перед повторением:

int max(int i, int j) {
    if (i >= j)
        return i;
    else
        return j;
}

int MaximumPath(int Mat[][N], int i, int j) {
    if (i >= N - 1) {
        // reached the last row
        return Mat[i][j];
    } else {
       // try all possible paths
       int v = MaximumPath(Mat, i + 1, j)
       if (j > 0)
           v = max(v, MaximumPath(Mat, i + 1, j - 1));
       if (j < N - 1)
           v = max(v, MaximumPath(Mat, i + 1, j + 1));
       return Max[i][j] + v;
    }
}