Рубрики

Минимальные начальные баллы для достижения пункта назначения

Дана сетка с каждой ячейкой, состоящей из положительных, отрицательных или отсутствующих точек, т.е. нулевых точек. Мы можем перемещаться по клетке, только если у нас есть положительные точки (> 0). Всякий раз, когда мы проходим через ячейку, очки в этой ячейке добавляются к нашим общим точкам. Нам нужно найти минимальные начальные точки для достижения ячейки (m-1, n-1) из (0, 0).

Ограничения:

  • Из ячейки (i, j) мы можем перейти к (i + 1, j) или (i, j + 1).
  • Мы не можем перейти от (i, j), если ваши общие баллы в (i, j) <= 0.
  • Мы должны достичь в (n-1, m-1) с минимальными положительными точками, т. Е.> 0.
  • Пример:

Input: points[m][n] = { {-2, -3,   3}, 
                        {-5, -10,  1}, 
                        {10,  30, -5} 
                      };
Output: 7
Explanation: 
7 is the minimum value to reach destination with 
positive throughout the path. Below is the path.

(0,0) -> (0,1) -> (0,2) -> (1, 2) -> (2, 2)

We start from (0, 0) with 7, we reach(0, 1) 
with 5, (0, 2) with 2, (1, 2) with 5, (2, 2)
with and finally we have 1 point (we needed 
greater than 0 points at the end). 

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

На первый взгляд, эта проблема выглядит аналогично Max / Min Cost Path , но максимальные полученные очки не гарантируют минимальные начальные очки. Кроме того, в текущей задаче обязательно, чтобы точки никогда не падали до нуля или ниже. Например, предположим, что существуют следующие два пути от исходной к целевой ячейке.

Мы можем решить эту проблему с помощью метода динамического программирования заполнения снизу вверх.

  • Начнем с того, что мы должны поддерживать 2D-массив dp того же размера, что и сетка, где dp [i] [j] представляет минимальные точки, которые гарантируют продолжение пути до пункта назначения до входа в ячейку (i, j). Очевидно, что dp [0] [0] является нашим окончательным решением. Следовательно, для этой проблемы нам нужно заполнить таблицу от нижнего правого угла до левого верхнего.
  • Теперь давайте определим минимальные точки, необходимые для выхода из ячейки (i, j) (помните, что мы движемся снизу вверх). Можно выбрать только два пути: (i + 1, j) и (i, j + 1). Конечно, мы выберем ячейку, в которой игрок может закончить остаток своего путешествия с меньшими начальными очками. Следовательно, мы имеем: min_Points_on_exit = min (dp [i + 1] [j], dp [i] [j + 1])

Теперь мы знаем, как вычислить min_Points_on_exit, но нам нужно заполнить таблицу dp [] [], чтобы получить решение в dp [0] [0].

Как вычислить dp [i] [j]?
Значение dp [i] [j] можно записать, как показано ниже.

dp [i] [j] = max (min_Points_on_exit — points [i] [j], 1)

Давайте посмотрим, как вышеприведенное выражение охватывает все случаи.

  • Если points [i] [j] == 0, то в этой ячейке ничего не получается; игрок может покинуть ячейку с теми же точками, с которыми он входит в комнату, т.е. dp [i] [j] = min_Points_on_exit.
  • Если points [i] [j] <0, то у игрока должно быть больше, чем min_Points_on_exit, прежде чем вводить (i, j), чтобы компенсировать потерянные очки в этой ячейке. Минимальная сумма компенсации составляет «- points [i] [j]», поэтому у нас есть dp [i] [j] = min_Points_on_exit — points [i] [j].
  • Если points [i] [j]> 0, то игрок может войти в (i, j) с точками всего min_Points_on_exit — points [i] [j]. так как он мог получить «очки [i] [j]» в этой клетке. Однако значение min_Points_on_exit — points [i] [j] может упасть до 0 или ниже в этой ситуации. Когда это происходит, мы должны обрезать значение до 1, чтобы убедиться, что dp [i] [j] остается положительным:
    dp [i] [j] = max (min_Points_on_exit — points [i] [j], 1).

Наконец, верните dp [0] [0], который является нашим ответом.

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

C ++

// C ++ программа для поиска минимальных начальных точек для достижения пункта назначения
#include<bits/stdc++.h>
#define R 3
#define C 3

  

using namespace std;

  

int minInitialPoints(int points[][C])

{

    // dp [i] [j] представляет минимальные начальные очки игрока

    // должно быть так, чтобы, когда начинается с ячейки (i, j) успешно

    // достигает ячейки назначения (m-1, n-1)

    int dp[R][C];

    int m = R, n = C;

  

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

    dp[m-1][n-1] = points[m-1][n-1] > 0? 1:

                   abs(points[m-1][n-1]) + 1;

  

    // Заполняем последнюю строку и последний столбец как базу для заполнения

    // вся таблица

    for (int i = m-2; i >= 0; i--)

         dp[i][n-1] = max(dp[i+1][n-1] - points[i][n-1], 1);

    for (int j = n-2; j >= 0; j--)

         dp[m-1][j] = max(dp[m-1][j+1] - points[m-1][j], 1);

  

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

    for (int i=m-2; i>=0; i--)

    {

        for (int j=n-2; j>=0; j--)

        {

            int min_points_on_exit = min(dp[i+1][j], dp[i][j+1]);

            dp[i][j] = max(min_points_on_exit - points[i][j], 1);

        }

     }

  

     return dp[0][0];

}

  
// Программа для водителя

int main()

{

  

    int points[R][C] = { {-2,-3,3},

                      {-5,-10,1},

                      {10,30,-5}

                    };

    cout << "Minimum Initial Points Required: "

         << minInitialPoints(points);

    return 0;

}

Джава

class min_steps

{

    static int minInitialPoints(int points[][],int R,int C)

    {

        // dp [i] [j] представляет минимальные начальные очки игрока

        // должно быть так, чтобы, когда начинается с ячейки (i, j) успешно

        // достигает ячейки назначения (m-1, n-1)

        int dp[][] = new int[R][C];

        int m = R, n = C;

       

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

        dp[m-1][n-1] = points[m-1][n-1] > 0? 1:

                       Math.abs(points[m-1][n-1]) + 1;

       

        // Заполняем последнюю строку и последний столбец как базу для заполнения

        // вся таблица

        for (int i = m-2; i >= 0; i--)

             dp[i][n-1] = Math.max(dp[i+1][n-1] - points[i][n-1], 1);

        for (int j = n-2; j >= 0; j--)

             dp[m-1][j] = Math.max(dp[m-1][j+1] - points[m-1][j], 1);

       

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

        for (int i=m-2; i>=0; i--)

        {

            for (int j=n-2; j>=0; j--)

            {

                int min_points_on_exit = Math.min(dp[i+1][j], dp[i][j+1]);

                dp[i][j] = Math.max(min_points_on_exit - points[i][j], 1);

            }

         }

       

         return dp[0][0];

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * / 

    public static void main (String args[])

    {

          int points[][] = { {-2,-3,3},

                      {-5,-10,1},

                      {10,30,-5}

                    };

          int R = 3,C = 3;

          System.out.println("Minimum Initial Points Required: "+

                                            minInitialPoints(points,R,C) );

    }

}/ * Этот код предоставлен Раджатом Мишрой * /

python3

# Python3 программа для поиска минимального начального
# очков, чтобы добраться до места назначения

import math as mt

R = 3

C = 3

  

def minInitialPoints(points):

    «»»

    dp [i] [j] представляет минимальный начальный

    очки игрок должен иметь так, чтобы при

    начинается с ячейки (i, j) успешно

    достигает ячейки назначения (m-1, n-1)

    «»»

    dp = [[0 for x in range(C + 1)] 

             for y in range(R + 1)]

    m, n = R, C

      

    if points[m - 1][n - 1] > 0:

        dp[m - 1][n - 1] = 1

    else:

        dp[m - 1][n - 1] = abs(points[m - 1][n - 1]) + 1

    «»»

    Заполните последний ряд и последний столбец как основание

    заполнить всю таблицу

    «»»

    for i in range (m - 2, -1, -1):

        dp[i][n - 1] = max(dp[i + 1][n - 1] -

                           points[i][n - 1], 1)

    for i in range (2, -1, -1):

        dp[m - 1][i] = max(dp[m - 1][i + 1] -

                           points[m - 1][i], 1)

    «»»

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

    «»»

    for i in range(m - 2, -1, -1):

        for j in range(n - 2, -1, -1):

            min_points_on_exit = min(dp[i + 1][j],

                                     dp[i][j + 1])

            dp[i][j] = max(min_points_on_exit -

                               points[i][j], 1)

              

    return dp[0][0

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

points = [[-2, -3, 3],

          [-5, -10, 1],

          [10, 30, -5]]

  

print("Minimum Initial Points Required:"

                minInitialPoints(points))

  

  
# Этот код предоставлен
# Мохит Кумар 29 (IIIT Гвалиор)

C #

// C # программа Минимальные начальные баллы
// чтобы добраться до места назначения

using System;

class GFG {

      

    static int minInitialPoints(int [,]points, 

                                 int R, int C)

    {

          

        // dp [i] [j] представляет

        // минимальные начальные точки

        // игрок должен иметь так

        // что когда начинается с

        // ячейка (i, j) успешно

        // достигает пункта назначения

        // ячейка (m-1, n-1)

        int [,]dp = new int[R,C];

        int m = R, n = C;

      

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

        dp[m - 1,n - 1] = points[m - 1, n - 1] > 0 ? 1:

                     Math.Abs(points[m - 1,n - 1]) + 1;

      

        // Заполняем последний ряд и последний

        // столбец как база для заполнения

        // вся таблица

        for (int i = m-2; i >= 0; i--)

            dp[i, n - 1] = Math.Max(dp[i + 1, n - 1] - 

                                points[i, n - 1], 1);

        for (int j = n - 2; j >= 0; j--)

            dp[m - 1, j] = Math.Max(dp[m - 1, j + 1] - 

                                points[m - 1, j], 1);

      

        // заполнить таблицу в

        // восходящая мода

        for(int i = m - 2; i >= 0; i--)

        {

            for (int j = n - 2; j >= 0; j--)

            {

                int min_points_on_exit = Math.Min(dp[i + 1, j], 

                                                  dp[i, j + 1]);

                dp[i, j] = Math.Max(min_points_on_exit - 

                                      points[i, j], 1);

            }

        }

      

        return dp[0, 0];

    }

  

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

    public static void Main ()

    {

        int [,]points = {{-2,-3,3},

                         {-5,-10,1},

                           {10,30,-5}};

        int R = 3,C = 3;

        Console.Write("Minimum Initial Points Required: "+

                           minInitialPoints(points, R, C));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска минимального начального
// указывает на пункт назначения

$R = 3;

$C = 3;

  

function minInitialPoints($points)

{

    // dp [i] [j] представляет минимум

    // начальные очки игрок должен иметь

    // чтобы началось с ячейки (i, j)

    // успешно достигает пункта назначения

    // ячейка (m-1, n-1)

    global $R;

    global $C;

    $dp[$R][$C] = array();

    $m = $R;

    $n = $C;

  

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

    $dp[$m - 1][$n - 1] = $points[$m - 1][$n - 1] > 0 ? 1 : 

                      abs($points[$m - 1][$n - 1]) + 1;

  

    // Заполняем последний ряд и последний столбец как

    // база для заполнения всей таблицы

    for ($i = $m - 2; $i >= 0; $i--)

        $dp[$i][$n - 1] = max($dp[$i + 1][$n - 1] - 

                              $points[$i][$n - 1], 1);

    for ($j = $n - 2; $j >= 0; $j--)

        $dp[$m - 1][$j] = max($dp[$m - 1][$j + 1] - 

                              $points[$m - 1][$j], 1);

  

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

    for ($i = $m - 2; $i >= 0; $i--)

    {

        for ($j = $n - 2; $j >= 0; $j--)

        {

            $min_points_on_exit = min($dp[$i + 1][$j], 

                                      $dp[$i][$j + 1]);

            $dp[$i][$j] = max($min_points_on_exit

                              $points[$i][$j], 1);

        }

    }

  

    return $dp[0][0];

}

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

$points = array(array(-2, -3, 3),

                array(-5, -10, 1),

                array(10, 30, -5));

              

echo "Minimum Initial Points Required: ",

               minInitialPoints($points);

  
// Этот код предоставлен akt_mit
?>


Выход:

Minimum Initial Points Required: 7

Эта статья предоставлена Gaurav Ahirwar . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Минимальные начальные баллы для достижения пункта назначения

0.00 (0%) 0 votes