Минимальная сумма пути треугольника ｜ Тематический месяц Go

Go

[Месяц изучения темы Golang] На выходных я попробовал ответить на несколько вопросов по динамическому программированию и отправил очень деликатную учебную версию. Ответ был очень хорошим. Далее я буду использовать два языка для вопросов по кодированию и чистке, а именно GO и JAVA , ребята, продолжайте писать вопросы.

Если вы не знакомы с динамическим программированием, перейдите к этой статье.\color{red}{Если вы не знакомы с динамическим программированием, перейдите к этой статье~}

Живите много дней - десять последовательных динамических программ - сверхтонкий анализ |

Вопрос очень интересный, не пожалеете! 😄😄😄 \color{green}{Это очень интересный вопрос, не пожалеете! 😄 😄 😄 ~}

Какие вопросы вы можете решить с помощью динамического программирования?

1. Считать

  • Сколько способов попасть в правый нижний угол
  • Сколькими способами можно выбрать k чисел да и сложить

2. Найдите максимальное и минимальное значения

  • Максимальная сумма чисел пути из левого верхнего угла в правый нижний угол
  • самая длинная восходящая длина подпоследовательности

3. Ищите существования

  • В игре со сбором камней обязательно ли выиграет тот, кто сделает первый ход?
  • Можно ли выбрать k чисел так, чтобы сумма была суммой

leetcode 120. Минимальная сумма пути треугольника

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

Каждый шаг может перемещаться только к соседним узлам в следующей строке. Смежные узлы здесь относятся к двум узлам, индекс которых совпадает с индексом предыдущего узла или равен индексу предыдущего узла + 1. То есть, если вы находитесь в индексе i текущей строки, следующий шаг может быть перемещен в индекс i или i + 1 следующей строки.

 

Пример 1:

Ввод: треугольник = [[2],[3,4],[6,5,7],[4,1,8,3]] Выход: 11 Объяснение: Как показано на следующей диаграмме:

image.png

Минимальная сумма путей сверху вниз равна 11 (т. е. 2 + 3 + 5 + 1 = 11). Пример 2:

Ввод: треугольник = [[-10]] Выход: -10  

намекать:

1 <= triangle.length <= 200

triangle[0].length == 1

triangle[i].length == triangle[i - 1].length + 1

-104 <= triangle[i][j] <= 104  

Передовой:

Сможете ли вы решить эту задачу, используя всего O(n) дополнительного пространства (n — общее количество строк в треугольнике)?

--

Код ссылки

языковая версия ГО

func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    f := make([][]int, n)
    for i := 0; i < n; i++ {
        f[i] = make([]int, n)
    }
    f[0][0] = triangle[0][0]
    for i := 1; i < n; i++ {
        f[i][0] = f[i - 1][0] + triangle[i][0]
        for j := 1; j < i; j++ {
            f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]
        }
        f[i][i] = f[i - 1][i - 1] + triangle[i][i]
    }
    ans := math.MaxInt32
    for i := 0; i < n; i++ {
        ans = min(ans, f[n-1][i])
    }
    return ans
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

Java-версия

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        // dp[i][j] 表示从点 (i, j) 到底边的最小路径和。
        int[][] dp = new int[n + 1][n + 1];
        // 从三角形的最后一行开始递推。
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}

Думать слишком просто? Кто-то еще просил нужно On, но теперь время сложности On2? Как его оптимизировать?

Начните рекурсивно с последней строки треугольника.

Используются только dp[i + 1][j]dp[i+1][j] и dp[i + 1][j + 1]dp[i+1][j+1] на следующей строке.

Представьте, что мы показываем минимальный путь в одной строке

Это временная сложность реализации On?

ГО версия

func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    f := make([]int, n+1)
    for i := n-1; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            f[j] = min(f[j], f[j + 1]) + triangle[i][j]
        }
    }
    return f[0]
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

JAVA-версия

 
   class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}

❤️❤️❤️❤️

Большое спасибо, что смогли увидеть эту статью.Если эта статья хорошо написана и вы думаете, что есть что-то, пожалуйста, ставьте лайк👍 Следуйте ❤️ Пожалуйста, поделитесь 👥 Это действительно полезно для меня, красавчик Оппа! ! !

Если в этом блоге есть какие-либо ошибки, пожалуйста, критикуйте и советуйте, это очень ценится!

В конце статьи мы недавно составили материал для интервью «Руководство по прохождению интервью по Java», в котором рассматриваются основные технологии Java, JVM, параллелизм Java, SSM, микросервисы, базы данных, структуры данных и многое другое. Как получить: GitHub github.com/Tingyu-Note…, следуйте официальной учетной записи для получения большего контента: Tingyu Notes, которые будут предоставляться один за другим.

Категории