Рубрики

Подсчитайте все возможные пути сверху вниз слева направо от матрицы mXn

Проблема состоит в том, чтобы подсчитать все возможные пути сверху вниз слева направо от матрицы mXn с ограничениями, которые из каждой ячейки вы можете перемещать только вправо или вниз

Примеры :

Input :  m = 2, n = 2;
Output : 2
There are two paths
(0, 0) -> (0, 1) -> (1, 1)
(0, 0) -> (1, 0) -> (1, 1)

Input :  m = 2, n = 3;
Output : 3
There are three paths
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2)
(0, 0) -> (0, 1) -> (1, 1) -> (1, 2)
(0, 0) -> (1, 0) -> (1, 1) -> (1, 2)

Мы обсудили решение для печати всех возможных путей , подсчет всех путей стал проще. Пусть NumberOfPaths (m, n) будет количеством путей для достижения номера строки m и номера столбца n в матрице, NumberOfPaths (m, n) может быть рекурсивно записано следующим образом.

C ++

// Программа на C ++ для подсчета всех возможных путей
// сверху вниз слева направо

  
#include <iostream>

using namespace std;

  
// Возвращает количество возможных путей для достижения ячейки в строке
// номер m и номер столбца n слева направо
// ячейка (ячейка на 1, 1)

int numberOfPaths(int m, int n)

{

    // Если либо номер строки является первым, либо столбцом

    // номер первый

    if (m == 1 || n == 1)

        return 1;

  

    // Если разрешены диагональные перемещения, то последний

    // требуется дополнение.

    return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);

    // + numberOfPaths (m-1, n-1);

}

  

int main()

{

    cout << numberOfPaths(3, 3);

    return 0;

}

Джава

// Java-программа для подсчета всех возможных путей
// сверху вниз слева направо

  

class GFG {

  

    // Возвращает количество возможных путей для достижения

    // ячейка с номером строки m и номером столбца n

    // из самой верхней левой ячейки (ячейка в 1, 1)

    static int numberOfPaths(int m, int n)

    {

        // Если задан номер строки первым или

        // номер столбца первый

        if (m == 1 || n == 1)

            return 1;

  

        // Если допустимы диагональные перемещения

        // требуется последнее добавление.

        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);

        // + numberOfPaths (m-1, n-1);

    }

  

    public static void main(String args[])

    {

        System.out.println(numberOfPaths(3, 3));

    }

}

  
// Этот код предоставлен Sumit Ghosh

питон

# Программа Python для подсчета всех возможных путей
# сверху слева внизу справа

  
# функция для возврата количества возможных путей
# чтобы добраться до ячейки с номером строки и столбца
# номер n от самого верхнего левого
# ячейка (ячейка на 1, 1)

def numberOfPaths(m, n):

# Если какой-либо номер строки является первым
# или заданный номер столбца является первым

    if(m == 1 or n == 1):

        return 1

  
# Если разрешены диагональные движения
# тогда последнее добавление
# требуется для.

    return numberOfPaths(m-1, n) + numberOfPaths(m, n-1)

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

m = 3

n = 3

print(numberOfPaths(m, n))

  
# Этот код предоставлен Адити Шарма

C #

// AC # программа для подсчета всех возможных путей
// сверху вниз слева направо

  

using System;

  

public class GFG {

    // Возвращает количество возможных путей для достижения

    // ячейка с номером строки m и номером столбца n

    // из самой верхней левой ячейки (ячейка в 1, 1)

    static int numberOfPaths(int m, int n)

    {

        // Если задан номер строки первым или

        // номер столбца первый

        if (m == 1 || n == 1)

            return 1;

  

        // Если допустимы диагональные перемещения

        // требуется последнее добавление.

        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);

        // + numberOfPaths (m-1, n-1);

    }

  

    static public void Main()

    {

        Console.WriteLine(numberOfPaths(3, 3));

    }

}

  
// Этот код предоставлен ajit

PHP

<?php

  
// Возвращает количество возможных путей
// достичь ячейки с номером строки m
// и номер столбца n из
// крайняя левая ячейка (ячейка 1, 1)

function numberOfPaths($m, $n)

{

      

    // Если задан номер строки

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

    // номер первый

    if ($m == 1 || $n == 1)

            return 1;

      

    // Если диагональные движения

    // разрешены последним

    // требуется дополнение.

    return numberOfPaths($m - 1, $n) + 

           numberOfPaths($m, $n - 1);

}

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

echo numberOfPaths(3, 3);

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


Выход:

6

Временная сложность вышеуказанного рекурсивного решения является экспоненциальной. Есть много пересекающихся подзадач. Мы можем нарисовать дерево рекурсии для numberOfPaths (3, 3) и увидеть много перекрывающихся подзадач. Дерево рекурсии было бы аналогично дереву рекурсии для задачи самой длинной общей подпоследовательности .
Таким образом, эта проблема имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и в других типичных задачах динамического программирования (DP) , повторных вычислений с одинаковыми подзадачами можно избежать, построив временный счетчик массивов [] [] снизу вверх, используя приведенную выше рекурсивную формулу.

C ++

// Программа на C ++ для подсчета всех возможных путей
// сверху вниз слева направо
#include <iostream>

using namespace std;

  
// Возвращает количество возможных путей для достижения ячейки в
// номер строки m и номер столбца n сверху
// крайняя левая ячейка (ячейка 1, 1)

int numberOfPaths(int m, int n)

{

    // Создаем 2D таблицу для хранения результатов подзадач

    int count[m][n];

  

    // Количество путей для достижения любой ячейки в первом столбце равно 1

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

        count[i][0] = 1;

  

    // Количество путей для достижения любой ячейки в первой строке равно 1

    for (int j = 0; j < n; j++)

        count[0][j] = 1;

  

    // Рассчитать количество путей для других ячеек в

    // восходящий способ с использованием рекурсивного решения

    for (int i = 1; i < m; i++) {

        for (int j = 1; j < n; j++)

  

            // Раскомментируя последнюю часть, код вычисляет итог

            // возможные пути, если разрешены диагональные движения

            count[i][j] = count[i - 1][j] + count[i][j - 1]; // + count [i-1] [j-1];

    }

    return count[m - 1][n - 1];

}

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

int main()

{

    cout << numberOfPaths(3, 3);

    return 0;

}

Джава

// Java-программа для подсчета всех возможных путей
// сверху вниз слева направо

class GFG {

    // Возвращает количество возможных путей для достижения

    // ячейка с номером строки m и номером столбца n из

    // крайняя левая ячейка (ячейка 1, 1)

    static int numberOfPaths(int m, int n)

    {

        // Создать 2D таблицу для хранения результатов

        // подзадач

        int count[][] = new int[m][n];

  

        // Количество путей для достижения любой ячейки в

        // первый столбец 1

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

            count[i][0] = 1;

  

        // Количество путей для достижения любой ячейки в

        // первый столбец 1

        for (int j = 0; j < n; j++)

            count[0][j] = 1;

  

        // Рассчитать количество путей для других

        // ячейки снизу вверх, используя

        // рекурсивное решение

        for (int i = 1; i < m; i++) {

            for (int j = 1; j < n; j++)

  

                // Раскомментируя последнюю часть

                // код, рассчитывающий общее количество возможных путей

                // если разрешены диагональные движения

                count[i][j] = count[i - 1][j] + count[i][j - 1]; // + count [i-1] [j-1];

        }

        return count[m - 1][n - 1];

    }

  

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

    public static void main(String args[])

    {

        System.out.println(numberOfPaths(3, 3));

    }

}

  
// Этот код предоставлен Sumit Ghosh

питон

# Программа Python для подсчета всех возможных путей
# сверху слева внизу справа

  
# Возвращает количество возможных путей для достижения ячейки
# на номер строки m и номер столбца n из
# крайняя левая ячейка (ячейка 1, 1)

def numberOfPaths(m, n):

    # Создать 2D таблицу для хранения

    # результаты подзадач

    count = [[0 for x in range(m)] for y in range(n)]

    

    # Количество путей для достижения любого

    # ячейка в первом столбце 1

    for i in range(m):

        count[i][0] = 1;

    

    # Количество путей для достижения любого

    # ячейка в первом столбце 1

    for j in range(n):

        count[0][j] = 1;

    

    # Рассчитать количество путей для других

    # ячейки снизу вверх

    # способ использования рекурсивного решения

    for i in range(1, m):

        for j in range(n):             

            count[i][j] = count[i-1][j] + count[i][j-1]

    return count[m-1][n-1]

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

m = 3

n = 3

print( numberOfPaths(m, n))

  
# Этот код предоставлен Адити Шарма

C #

// AC # программа для подсчета всех возможных путей
// сверху вниз слева направо

using System;

  

public class GFG {

  

    // Возвращает количество возможных путей для достижения

    // ячейка с номером строки m и номером столбца n из

    // крайняя левая ячейка (ячейка 1, 1)

    static int numberOfPaths(int m, int n)

    {

        // Создать 2D таблицу для хранения результатов

        // подзадач

        int[, ] count = new int[m, n];

  

        // Количество путей для достижения любой ячейки в

        // первый столбец 1

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

            count[i, 0] = 1;

  

        // Количество путей для достижения любой ячейки в

        // первый столбец 1

        for (int j = 0; j < n; j++)

            count[0, j] = 1;

  

        // Рассчитать количество путей для других

        // ячейки снизу вверх, используя

        // рекурсивное решение

        for (int i = 1; i < m; i++) {

            for (int j = 1; j < n; j++)

  

                // Раскомментируя последнюю часть

                // код, рассчитывающий общее количество возможных путей

                // если разрешены диагональные движения

                count[i, j] = count[i - 1, j] + count[i, j - 1]; // + count [i-1] [j-1];

        }

        return count[m - 1, n - 1];

    }

  

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

    static public void Main()

    {

        Console.WriteLine(numberOfPaths(3, 3));

    }

}

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

PHP

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

  
// Возвращает количество возможных путей к
// достигаем ячейки по номеру строки m и столбцу
// номер n сверху слева
// ячейка (ячейка на 1, 1)

function numberOfPaths($m, $n)

{

    // Создать 2D таблицу для хранения

    // результаты подзадач

    $count = array();

  

    // Количество путей до любой ячейки

    // в первом столбце 1

    for ($i = 0; $i < $m; $i++)

        $count[$i][0] = 1;

  

    // Количество путей до любой ячейки

    // в первом столбце 1

    for ($j = 0; $j < $n; $j++)

        $count[0][$j] = 1;

  

    // Рассчитать количество путей для других

    // ячейки снизу вверх, используя

    // рекурсивное решение

    for ($i = 1; $i < $m; $i++)

    {

        for ($j = 1; $j < $n; $j++)

  

            // Раскомментируя последнюю часть

            // код рассчитал максимально возможную

            // пути, если разрешены диагональные движения

            $count[$i][$j] = $count[$i - 1][$j] + 

                             $count[$i][$j - 1]; // + count [i-1] [j-1];

    }

    return $count[$m - 1][$n - 1];

}

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

echo numberOfPaths(3, 3);

  
// Этот код добавлен
// Мукул Сингх
?>


Выход:

6

Временная сложность вышеуказанного динамического программного решения составляет O (mn).
Пространственная сложность вышеупомянутого решения O (mn).

Оптимизация пространства решения DP.
Приведенное выше решение более интуитивно понятно, но мы также можем уменьшить пространство на O (n); где n — размер столбца.

C ++

#include <bits/stdc++.h>

  

using namespace std;

  
// Возвращает количество возможных путей для достижения
// ячейка с номером строки m и номером столбца n из
// крайняя левая ячейка (ячейка 1, 1)

int numberOfPaths(int m, int n)

{

    // Создаем одномерный массив для хранения результатов подзадач

    int dp[n] = { 1 };

    dp[0] = 1;

  

    for (int i = 0; i < m; i++) {

        for (int j = 1; j < n; j++) {

            dp[j] += dp[j - 1];

        }

    }

  

    return dp[n - 1];

}

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

int main()

{

    cout << numberOfPaths(3, 3);

}

  
// Этот код предоставлен Мохит Кумар 29

Джава

class GFG {

    // Возвращает количество возможных путей для достижения

    // ячейка с номером строки m и номером столбца n из

    // крайняя левая ячейка (ячейка 1, 1)

    static int numberOfPaths(int m, int n)

    {

        // Создаем одномерный массив для хранения результатов подзадач

        int[] dp = new int[n];

        dp[0] = 1;

  

        for (int i = 0; i < m; i++) {

            for (int j = 1; j < n; j++) {

                dp[j] += dp[j - 1];

            }

        }

  

        return dp[n - 1];

    }

  

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

    public static void main(String args[])

    {

        System.out.println(numberOfPaths(3, 3));

    }

}

python3

# Возвращает количество возможных путей
# достичь ячейки в строке номер m и
# столбец номер n сверху
# крайняя левая ячейка (ячейка на 1, 1)

def numberOfPaths(p, q):

      

    # Создать 1D массив для хранения

    # результаты подзадач

    dp = [1 for i in range(q)]

    for i in range(p - 1):

        for j in range(1, q):

            dp[j] += dp[j - 1]

    return dp[q - 1]

  
Код водителя

print(numberOfPaths(3, 3))

  
# Этот код добавлен
# Анкит Ядав

C #

using System;

  

class GFG {

    // Возвращает количество возможных путей

    // достичь ячейки с номером строки m

    // и номер столбца n из

    // крайняя левая ячейка (ячейка 1, 1)

    static int numberOfPaths(int m, int n)

    {

        // Создать 1D массив для хранения

        // результаты подзадач

        int[] dp = new int[n];

        dp[0] = 1;

  

        for (int i = 0; i < m; i++) {

            for (int j = 1; j < n; j++) {

                dp[j] += dp[j - 1];

            }

        }

  

        return dp[n - 1];

    }

  

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

    public static void Main()

    {

        Console.Write(numberOfPaths(3, 3));

    }

}

  
// Этот код добавлен
// ChitraNayal

PHP

<?php
// Возвращает количество возможных путей к
// достигаем ячейки с номером строки m
// столбец номер n сверху
// крайняя левая ячейка (ячейка 1, 1)

function numberOfPaths($m, $n)

{

    // Создать 1D массив для хранения

    // результаты подзадач

    $dp = array();

    $dp[0] = 1;

  

    for ($i = 0; $i < $m; $i++)

    {

    for ($j = 1; $j < $n; $j++)

    {

        $dp[$j] += $dp[$j - 1];

    }

    }

  

    return $dp[$n - 1];

}

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

echo numberOfPaths(3, 3);

  
// Этот код добавлен
// Аканкша Рай
?>


Выход:

6

Этот код предоставлен Вивеком Сингхом

Обратите внимание, что количество также можно рассчитать по формуле (m-1 + n-1)! / (M-1)! (N-1) !.
Другой подход: (с использованием комбинаторики). В этом подходе мы должны вычислить m + n-2 C n-1, который будет (m + n-2)! / (n-1)! (М-1)!

C ++

// Программа на C ++ для подсчета всех возможных путей из
// сверху вниз, сверху вниз, используя комбинаторику

  
#include <iostream>

using namespace std;

  

int numberOfPaths(int m, int n)

{

    // Здесь мы должны вычислить m + n-2 C n-1

    // который будет (m + n-2)! / (n-1)! (М-1)!

    int path = 1;

    for (int i = n; i < (m + n - 1); i++) {

        path *= i;

        path /= (i - n + 1);

    }

    return path;

}

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

int main()

{

    cout << numberOfPaths(3, 3);

    return 0;

}

  
// Этот код предложен Картиком Сапрой

Джава

// Java-программа для подсчета всех возможных путей из
// сверху вниз, сверху вниз, используя комбинаторику

class GFG {

  

    static int numberOfPaths(int m, int n)

    {

        // Здесь мы должны вычислить m + n-2 C n-1

        // который будет (m + n-2)! / (n-1)! (М-1)!

        int path = 1;

        for (int i = n; i < (m + n - 1); i++) {

            path *= i;

            path /= (i - n + 1);

        }

        return path;

    }

  

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

    public static void main(String[] args)

    {

        System.out.println(numberOfPaths(3, 3));

    }

}

  
// Этот код предоставлен Code_Mech.

python3

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

def numberOfPaths(m, n) :

  

    # Мы должны вычислить m + n-2 C n-1 здесь

    # который будет (m + n-2)! / (n-1)! (М-1)! путь = 1;

    for i in range(n, (m + n - 1)):

        path *= i;

        path //= (i - n + 1);

      

    return path;

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

print(numberOfPaths(3, 3));

  
# Этот код добавлен
# от Akanksha Rai

C #

// C # программа для подсчета всех возможных путей из
// сверху вниз, сверху вниз, используя комбинаторику

using System;

  

class GFG {

  

    static int numberOfPaths(int m, int n)

    {

        // Здесь мы должны вычислить m + n-2 C n-1

        // который будет (m + n-2)! / (n-1)! (М-1)!

        int path = 1;

        for (int i = n; i < (m + n - 1); i++) {

            path *= i;

            path /= (i - n + 1);

        }

        return path;

    }

  

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

    public static void Main()

    {

        Console.WriteLine(numberOfPaths(3, 3));

    }

}

  
// Этот код предоставлен Code_Mech.

PHP

<?php

  
// PHP программа для подсчета всех возможных путей из
// сверху вниз, сверху вниз, используя комбинаторику

function numberOfPaths($m, $n

{

    // Здесь мы должны вычислить m + n-2 C n-1

    // который будет (m + n-2)! / (n-1)! (М-1)!

    $path = 1;

    for ($i = $n; $i < ($m + $n - 1); $i++)

    {

        $path *= $i;

        $path /= ($i - $n + 1);

    }

    return $path;

}

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

    echo(numberOfPaths(3, 3));

}

  
// Этот код предоставлен Code_Mech.


Выход:

6

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

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

Подсчитайте все возможные пути сверху вниз слева направо от матрицы mXn

0.00 (0%) 0 votes