64. Minimum Path Sum

LeetCode medium original: C# #array #csharp #dynamic-programming #leetcode #math #matrix #medium

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

LeetCode Static

На сетке размером m на n, заполненной неотрицательными числами, find путь от верхнего левого угла до нижнего правого, который минимизирует сумму всех чисел вдоль своего пути.

Примечание: Вы можете перемещаться только вниз или вправо в любой момент времени.

예제:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]

Output: 7

Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

C# 해법

매칭됨/원본

public class Solution {
    public int MinPathSum(int[][] grid) {
        int[][] dp = new int [grid.Length][];
        for (int i = 0; i < grid.Length; i++) dp[i] = new int[grid[0].Length];
        for (int i = grid.Length - 1; i >= 0; i--) {
            for (int j = grid[0].Length - 1; j >= 0; j--) {
                if (i == grid.Length - 1 && j != grid[0].Length - 1)
                    dp[i][j] = grid[i][j] + dp[i][j + 1];
                else if (j == grid[0].Length - 1 && i != grid.Length - 1)
                    dp[i][j] = grid[i][j] + dp[i + 1][j];
                else if (j != grid[0].Length - 1 && i != grid.Length - 1)
                    dp[i][j] =
                        grid[i][j] + Math.Min(dp[i + 1][j], dp[i][j + 1]);
                else
                    dp[i][j] = grid[i][j];
            }
        }
        return dp[0][0];
    }
}

C++ 해법

자동 초안, 제출 전 검토

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinPathSum(int[][] grid) {
        int[][] dp = new int [grid.size()][];
        for (int i = 0; i < grid.size(); i++) dp[i] = new int[grid[0].size()];
        for (int i = grid.size() - 1; i >= 0; i--) {
            for (int j = grid[0].size() - 1; j >= 0; j--) {
                if (i == grid.size() - 1 && j != grid[0].size() - 1)
                    dp[i][j] = grid[i][j] + dp[i][j + 1];
                else if (j == grid[0].size() - 1 && i != grid.size() - 1)
                    dp[i][j] = grid[i][j] + dp[i + 1][j];
                else if (j != grid[0].size() - 1 && i != grid.size() - 1)
                    dp[i][j] =
                        grid[i][j] + min(dp[i + 1][j], dp[i][j + 1]);
                else
                    dp[i][j] = grid[i][j];
            }
        }
        return dp[0][0];
    }
}

Java 해법

매칭됨/원본

public class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                if (i == grid.length - 1 && j != grid[0].length - 1) dp[i][j] =
                    grid[i][j] + dp[i][j + 1];
                else if (
                    j == grid[0].length - 1 && i != grid.length - 1
                ) dp[i][j] = grid[i][j] + dp[i + 1][j];
                else if (
                    j != grid[0].length - 1 && i != grid.length - 1
                ) dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
                else dp[i][j] = grid[i][j];
            }
        }
        return dp[0][0];
    }
}

JavaScript 해법

매칭됨/원본

var minPathSum = function (grid) {
    let dp = new Array(grid.length)
        .fill()
        .map(() => new Array(grid[0].length).fill(0));
    for (let i = grid.length - 1; i >= 0; i--) {
        for (let j = grid[0].length - 1; j >= 0; j--) {
            if (i === grid.length - 1 && j !== grid[0].length - 1)
                dp[i][j] = grid[i][j] + dp[i][j + 1];
            else if (j === grid[0].length - 1 && i !== grid.length - 1)
                dp[i][j] = grid[i][j] + dp[i + 1][j];
            else if (j !== grid[0].length - 1 && i !== grid.length - 1)
                dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
            else dp[i][j] = grid[i][j];
        }
    }
    return dp[0][0];
};

Python 해법

매칭됨/원본

class Solution:
    def minPathSum(self, grid):
        m = len(grid)
        n = len(grid[0])
        dp = [[0] * n for _ in range(m)]
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i == m - 1 and j != n - 1:
                    dp[i][j] = grid[i][j] + dp[i][j + 1]
                elif j == n - 1 and i != m - 1:
                    dp[i][j] = grid[i][j] + dp[i + 1][j]
                elif j != n - 1 and i != m - 1:
                    dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1])
                else:
                    dp[i][j] = grid[i][j]
        return dp[0][0]

Go 해법

매칭됨/원본

func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if i == m-1 && j != n-1 {
                dp[i][j] = grid[i][j] + dp[i][j+1]
            } else if j == n-1 && i != m-1 {
                dp[i][j] = grid[i][j] + dp[i+1][j]
            } else if j != n-1 && i != m-1 {
                dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j+1])
            } else {
                dp[i][j] = grid[i][j]
            }
        }
    }
    return dp[0][0]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Algorithm

1️⃣

Инициализация дополнительной матрицы dp такого же размера, как и исходная матрица. В этой матрице dp(i, j) представляет минимальную сумму пути от индекса (i, j) до самого правого нижнего elementа. Начинаем с инициализации самого правого нижнего elementа dp как последнего elementа заданной матрицы.

2️⃣

Для каждого elementа, начиная с правого нижнего угла, мы обходим матрицу в обратном порядке и заполняем её требуемыми минимальными суммами. Важно отметить, что на каждом elementе мы можем перемещаться либо вправо, либо вниз.

3️⃣

Для заполнения минимальной суммы используется уравнение: dp(i, j) = grid(i, j) + min(dp(i+1, j), dp(i, j+1)), с учётом граничных условий.

😎

Vacancies for this task

활성 채용 with overlapping task tags are 표시됨.

전체 채용

아직 활성 채용이 없습니다.