Рубрики

Максимальная сумма пути в матрице сверху вниз и обратно

Дана матрица размерности N * M. Задача состоит в том, чтобы найти максимальную сумму пути от arr [0] [0] до arr [N — 1] [M — 1] и обратно от arr [N — 1] [M — 1] до arr [0] [0 ] .

На пути от arr [0] [0] до arr [N — 1] [M — 1] вы можете перемещаться в направлении вниз и вправо, а также на пути от arr [N — 1] [M — 1] до arr [0] [0] , вы можете перемещаться в верхнем и левом направлениях.

Примечание : оба пути не должны быть равными, т. Е. Должна быть хотя бы одна ячейка arr [i] [j], которая не является общей для обоих путей.

Примеры:

Input: 
mat[][]= {{1, 0, 3, -1},
          {3, 5, 1, -2},
          {-2, 0, 1, 1},
          {2, 1, -1, 1}}
Output: 16
Maximum sum on path from arr[0][0] to arr[3][3] = 1 + 3 + 5 + 1 + 1 + 1 + 1 = 13 Maximum sum on path from arr[3][3] to arr[0][0] = 3 Total path sum = 13 + 3 = 16 Input: mat[][]= {{1, 0}, {1, 1}} Output: 3

Подход: эта проблема в некоторой степени похожа на проблему пути с минимальными затратами, за исключением того, что в данной задаче находятся два пути с максимальной суммой Кроме того, мы должны позаботиться о том, чтобы клетки на обоих путях вносили только один раз в сумму.
Первое, на что следует обратить внимание, это то, что путь от arr [N — 1] [M — 1] до arr [0] [0] — не что иное, как другой путь от arr [0] [0] до arr [N — 1] [M — 1] . Итак, нам нужно найти два пути от arr [0] [0] до arr [N — 1] [M — 1] с максимальной суммой.
Подходя аналогично задаче пути минимальной стоимости, мы начинаем оба пути с arr [0] [0] вместе и возвращаемся к соседним ячейкам матрицы, пока не достигнем arr [N — 1] [M — 1] . Чтобы убедиться, что ячейка не вносит вклад более одного раза, мы проверяем, являются ли текущие ячейки на обоих путях одинаковыми или нет. Если они одинаковы, он добавляется в ответ только один раз.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Матрица ввода

int n = 4, m = 4;

int arr[4][4] = { { 1, 0, 3, -1 },

                  { 3, 5, 1, -2 },

                  { -2, 0, 1, 1 },

                  { 2, 1, -1, 1 } };

  
// матрица DP

int cache[5][5][5];

  
// Функция для возврата суммы ячеек
// arr [i1] [j1] и arr [i2] [j2]

int sum(int i1, int j1, int i2, int j2)

{

    if (i1 == i2 && j1 == j2) {

        return arr[i1][j1];

    }

    return arr[i1][j1] + arr[i2][j2];

}

  
// Рекурсивная функция для возврата
// требуемый путь максимальной стоимости

int maxSumPath(int i1, int j1, int i2)

{

  

    // номер столбца второго пути

    int j2 = i1 + j1 - i2;

  

    // Базовый вариант

    if (i1 >= n || i2 >= n || j1 >= m || j2 >= m) {

        return 0;

    }

  

    // Если уже вычислено, возврат из матрицы DP

    if (cache[i1][j1][i2] != -1) {

        return cache[i1][j1][i2];

    }

    int ans = INT_MIN;

  

    // Повторяем для соседних ячеек обоих путей вместе

    ans = max(ans, maxSumPath(i1 + 1, j1, i2 + 1) + sum(i1, j1, i2, j2));

    ans = max(ans, maxSumPath(i1, j1 + 1, i2) + sum(i1, j1, i2, j2));

    ans = max(ans, maxSumPath(i1, j1 + 1, i2 + 1) + sum(i1, j1, i2, j2));

    ans = max(ans, maxSumPath(i1 + 1, j1, i2) + sum(i1, j1, i2, j2));

  

    // Сохранение результата в матрицу DP для текущего состояния

    cache[i1][j1][i2] = ans;

  

    return ans;

}

  
// Код драйвера

int main()

{

    memset(cache, -1, sizeof(cache));

    cout << maxSumPath(0, 0, 0);

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG

      
// Матрица ввода

static int n = 4, m = 4;

static int arr[][] = { { 1, 0, 3, -1 },

                { 3, 5, 1, -2 },

                { -2, 0, 1, 1 },

                { 2, 1, -1, 1 } };

  
// матрица DP

static int cache[][][] = new int[5][5][5];

  
// Функция для возврата суммы ячеек
// arr [i1] [j1] и arr [i2] [j2]

static int sum(int i1, int j1, int i2, int j2)

{

    if (i1 == i2 && j1 == j2) 

    {

        return arr[i1][j1];

    }

    return arr[i1][j1] + arr[i2][j2];

}

  
// Рекурсивная функция для возврата
// требуемый путь максимальной стоимости

static int maxSumPath(int i1, int j1, int i2)

{

  

    // номер столбца второго пути

    int j2 = i1 + j1 - i2;

  

    // Базовый вариант

    if (i1 >= n || i2 >= n || j1 >= m || j2 >= m) 

    {

        return 0;

    }

  

    // Если уже вычислено, возврат из матрицы DP

    if (cache[i1][j1][i2] != -1

    {

        return cache[i1][j1][i2];

    }

    int ans = Integer.MIN_VALUE;

  

    // Повторяем для соседних ячеек обоих путей вместе

    ans = Math.max(ans, maxSumPath(i1 + 1, j1, i2 + 1) + sum(i1, j1, i2, j2));

    ans = Math.max(ans, maxSumPath(i1, j1 + 1, i2) + sum(i1, j1, i2, j2));

    ans = Math.max(ans, maxSumPath(i1, j1 + 1, i2 + 1) + sum(i1, j1, i2, j2));

    ans = Math.max(ans, maxSumPath(i1 + 1, j1, i2) + sum(i1, j1, i2, j2));

  

    // Сохранение результата в матрицу DP для текущего состояния

    cache[i1][j1][i2] = ans;

  

    return ans;

}

  
// Код драйвера

public static void main(String args[])

{

    // установить начальное значение

    for(int i=0;i<5;i++)

    for(int i1=0;i1<5;i1++)

    for(int i2=0;i2<5;i2++)

    cache[i][i1][i2]=-1;

      

    System.out.println( maxSumPath(0, 0, 0));

}
}

  
// Этот код предоставлен Арнабом Кунду

python3

# Python 3 реализация подхода

import sys

  
# Матрица ввода

n = 4

m = 4

arr = [[1, 0, 3, -1],

    [3, 5, 1, -2],

    [-2, 0, 1, 1],

    [2, 1, -1, 1]]

  
# Матрица DP

cache = [[[-1 for i in range(5)] for j in range(5)] for k in range(5)]

  
# Функция для возврата суммы ячеек
# arr [i1] [j1] и arr [i2] [j2]

def sum(i1, j1, i2, j2):

    if (i1 == i2 and j1 == j2):

        return arr[i1][j1]

    return arr[i1][j1] + arr[i2][j2]

  
# Рекурсивная функция для возврата
# требуется максимальная стоимость пути

def maxSumPath(i1, j1, i2):

      

    # Номер столбца второго пути

    j2 = i1 + j1 - i2

  

    # Базовый вариант

    if (i1 >= n or i2 >= n or j1 >= m or j2 >= m):

        return 0

  

    # Если уже рассчитано, возврат из матрицы DP

    if (cache[i1][j1][i2] != -1):

        return cache[i1][j1][i2]

    ans = -sys.maxsize-1

  

    # Повторяется для соседних ячеек обоих путей вместе

    ans = max(ans, maxSumPath(i1 + 1, j1, i2 + 1) + sum(i1, j1, i2, j2))

    ans = max(ans, maxSumPath(i1, j1 + 1, i2) + sum(i1, j1, i2, j2))

    ans = max(ans, maxSumPath(i1, j1 + 1, i2 + 1) + sum(i1, j1, i2, j2))

    ans = max(ans, maxSumPath(i1 + 1, j1, i2) + sum(i1, j1, i2, j2))

  

    # Сохранение результата в матрицу DP для текущего состояния

    cache[i1][j1][i2] = ans

  

    return ans

  
# Код драйвера

if __name__ == '__main__':

    print(maxSumPath(0, 0, 0))

  
# Этот код предоставлен
# Surendra_Gangwar

C #

// C # реализация подхода

using System;

  

class GFG

      
// Матрица ввода

static int n = 4, m = 4;

static int [,]arr = { { 1, 0, 3, -1 },

                { 3, 5, 1, -2 },

                { -2, 0, 1, 1 },

                { 2, 1, -1, 1 } };

  
// матрица DP

static int [,,]cache = new int[5, 5, 5];

  
// Функция для возврата суммы ячеек
// arr [i1] [j1] и arr [i2] [j2]

static int sum(int i1, int j1, int i2, int j2)

{

    if (i1 == i2 && j1 == j2) 

    {

        return arr[i1, j1];

    }

    return arr[i1, j1] + arr[i2, j2];

}

  
// Рекурсивная функция для возврата
// требуемый путь максимальной стоимости

static int maxSumPath(int i1, int j1, int i2)

{

  

    // номер столбца второго пути

    int j2 = i1 + j1 - i2;

  

    // Базовый вариант

    if (i1 >= n || i2 >= n || j1 >= m || j2 >= m) 

    {

        return 0;

    }

  

    // Если уже вычислено, возврат из матрицы DP

    if (cache[i1, j1, i2] != -1) 

    {

        return cache[i1, j1, i2];

    }

    int ans = int.MinValue;

  

    // Повторяем для соседних ячеек обоих путей вместе

    ans = Math.Max(ans, maxSumPath(i1 + 1, j1, i2 + 1) + sum(i1, j1, i2, j2));

    ans = Math.Max(ans, maxSumPath(i1, j1 + 1, i2) + sum(i1, j1, i2, j2));

    ans = Math.Max(ans, maxSumPath(i1, j1 + 1, i2 + 1) + sum(i1, j1, i2, j2));

    ans = Math.Max(ans, maxSumPath(i1 + 1, j1, i2) + sum(i1, j1, i2, j2));

  

    // Сохранение результата в матрицу DP для текущего состояния

    cache[i1, j1, i2] = ans;

  

    return ans;

}

  
// Код драйвера

public static void Main(String []args)

{

    // установить начальное значение

    for(int i = 0; i < 5; i++)

        for(int i1 = 0; i1 < 5; i1++)

            for(int i2 = 0; i2 < 5; i2++)

                cache[i,i1,i2]=-1;

      

    Console.WriteLine( maxSumPath(0, 0, 0));

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

16

Сложность времени: O ((N 2 ) * M)

Рекомендуемые посты:

Максимальная сумма пути в матрице сверху вниз и обратно

0.00 (0%) 0 votes