Подъем по лестнице с динамическим программированием｜Go Theme Month

Go

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

😄

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

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

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

1. Считать

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

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

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

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

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

leetcode 70: подъем по лестнице

Предположим, вы поднимаетесь по лестнице. Вам нужно n шагов, чтобы добраться до крыши.

каждый раз, когда ты можешьвзбираться1или2Кусок\color{red}{Поднимитесь на 1 или 2~}шаги. Сколькими способами можно добраться до вершины здания?

Примечание. Данное n является положительным целым числом.

Пример 1:

Вход: 2 выход: 2 Пояснение: Есть два способа подняться на крышу.

  1. Уровень 1 + Уровень 1
  2. Уровень 2

Пример 2:

Вход: 3 выход: 3 Пояснение: Есть три способа подняться на вершину здания.

  1. Уровень 1 + Уровень 1 + Уровень 1
  2. Уровень 1 + Уровень 2
  3. Уровень 2 + Уровень 1

После прочтения предыдущих шагов решения проблемы, шаг за шагом

2.1 Компонент динамического программирования 1: определение состояния

Проще говоря, при решении динамического программирования вам нужно открыть массив, что представляет собой каждый элемент массива f[i] или f[i][j] аналогично тому, что представляют x, y, z в математических задачах.

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

последний шаг

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

Очевидно, что это не что иное, как восхождение на первую ступеньку или восхождение на вторую ступеньку.

Поскольку существует n лестниц, окончательный случай: n - 1 или n -2.

подзадача

Для подзадачи это вычислить проблему до последнего шага.Если мы вычислим результат предыдущей задачи и сохраним его, мы можем решить ее, запросив последний шаг.

то есть

Подзадача трансформируется в следующую: мы устанавливаем в общей сложности k способов подняться на вершину здания, затем

k = f(n) = f(n-1) + f(n-2)

k - 1 = f(n - 1) = f(n-2) + f(n-3)

...

2.2 Компонент динамического программирования 2: уравнения перехода

Для любых n ступеней лестницы:

f(n) = f(n-1) + f(n-2)

2.3 Компонент динамического программирования 3: начальные условия и граничные случаи

Начальное условие: n — целое положительное число.

Мы начали восхождение с уровня 0, поэтому с уровня 0 на уровень 0 мы видим, что есть только одно решение, а именно е (0) = 1

Восхождение с уровня 0 на уровень 1 также можно рассматривать как единственное решение, а именно е (1) = 1

3.4 Компонент динамического программирования 4: Порядок вычислений

Рассчитывайте в соответствии с этим!

Код ссылки

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

func climbStairs(n int) int {

	dp := make([]int, n+1)
	dp[0] = 1
	dp[1] = 1

	for i := 2; i <= n; i++ {
	   dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

JAVA-версия

 public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
 }

см. далеескользящий массивкак?

Мы определяем p как эквивалентное n-1, q как эквивалентное n-2, r = сколько способов нужно, чтобы перейти к следующему шагу = p + q

Начальное условие не меняется r = 1, что означает, что требуется 1 раз, чтобы перейти с уровня 0 на уровень 0 или уровень 1.

image.png

image.png

Код ссылки

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

func climbStairs1(n int) int {
	p := 0
	q := 0
	r := 1
	for i := 1; i <= n; i++ {
		p = q
		q = r
		r = p + q
	}
	return r

}

JAVA-версия

 public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
}

❤️❤️❤️❤️

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

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

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

Категории