Заметки по изучению алгоритмов (8) - Основы динамического программирования

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

Динамическое программирование:

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

Возникают проблемы с пониманием динамического программирования:

Эта задача возникает в случае подъема по лестнице. Всего у лестницы n ступеней, и на каждой ступеньке можно подняться на 1 или 2 ступеньки. Сколько существует вариантов подняться на вершину здания?

Анализ: (насильственное отступление)

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

пример кода：


# python代码示例
def backrack(choices,state,n,res) :
    if state == n :
        res[0] += 1 
    for choice in choices :
        if state + choice > n :
            continue
        backrack(choices,state+choice,n,res)
def climbing_stairs_backrack(n) :
    choices = [1,2]
    state = 0
    res = [0]
    backrack(choices,state,n,res)
    return res[0]
n = int(input())
print(climbing_stairs_backrack(n))


// c++代码示例
void backrack(vector<int> &choices, int state, int n, vector<int> &res)
{
    if (state == n )
    {
        res[0]++ ;
    }
    for (auto &choice : choices)
    {
        if (state + choice > n)
        {
            continue ;
        }
        backrack(choices, state + choice, n, res)
    }
}
 
int climbingStairsBackrack(int n)
{    
    vector<int> choices = {1 , 2 } ;
    int state = 0 ;
    vector<int> res = [0] ;
    backrack(choices, state, n, res) ;
    return res[0] ;
}

Жестокий поиск:

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

Мы можем попытаться проанализировать этот вопрос с точки зрения декомпозиции проблемы. Предположим, что существуют решения dp[i] для подъема на i-й уровень, тогда dp[i] — исходная задача, а ее подзадачи включают в себя:

дп[i-1]，дп[i-2]，дп[1]，дп[2]

Поскольку в каждом раунде мы можем подняться только на 1 или 2 ступеньки, то, стоя на i-й лестнице, в предыдущем раунде мы могли стоять только на i-1 или i-2 ступеньках. Другими словами, мы можем перейти только с i-1-го или i-2-го уровня на i-й уровень.

Отсюда можно сделать важный вывод: количество планов, поднявшихся на i-1-й уровень плюс количество планов, поднявшихся на i-2-й уровень, равно количеству планов, поднявшихся на i-й уровень. -й уровень. Формула выглядит следующим образом:

дп[i] = дп[i-1] + дп[i-2]

Это означает, что в задаче подъема по зданию существует рекурсивная связь, и исходную задачу можно решить путем построения решений подзадач.

Пример кода Dfs: (поиск)


# python 代码示例
def dfs(i : int) -> int :
    if i == 1 or i == 2 :
        return i
    count = dfs(i - 1) + dfs(i - 2)
    return count
def climbing_stairs_dfs(n : int) -> int :
    retunr dfs(n)


// c++ 代码示例
int dfs(int i)
{
    if (i == 1 || i == 2)
    {
        return i ;
    }
    int count = dfs(i - 1) + dfs(i - 2);
    return count ;
}
int climbingStairsDFS(int n)
{
    retunr dfs(n) ;
}

Рекурсивное дерево, созданное с помощью сильной рекурсии：

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

Мемоизированный поиск:

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

Когда dp[i] вычисляется впервые, он записывается в nem[i] для последующего использования.
При повторном вычислении dp[i] результат получается непосредственно в nem[i], чтобы избежать повторных вычислений подзадач.

Пример кода:


# python 代码示例
def dfs(i : int, mem : list[int]) -> int :
    if i == 1 or i == 2 :
        return i
    if mem[i] != -1 :
        return mem[i]
    count = dfs(i - 1, mem) + dfs(i - 2, mem)
    # 记录dfs(i)
    mem[i] = count
    return count
def climbing_stairs_dfs_mem(n : int) -> int :
    mem = [-1] * (n + 1)
    return dfs(n, mem)


// c++ 代码示例
int dfs(int i, vector<int> &mem)
{
    if (i == 1 || i == 2)
    {
        return i ;
    }
    if (mem != -1)
    {
        return mem[i] ;
    }
    int count = dfs(i - 1, mem) + dfs(i - 2, mem) ;
    mem[i] = count ;
    return count ;
}
int climbingStairsDFSMem(int n)
{
    vector<int> mem(n + 1, -1) ;
    return dfs(n, mem) ; 
}

После мемоизации все перекрывающиеся подзадачи вычисляются только один раз, а временная сложность оптимизируется до O(n).

Динамическое программирование:

Мемоизированный поиск — это метод «сверху вниз». Мы начинаем с исходной проблемы (корневой узел) и рекурсивно разлагаем более крупные подзадачи на более мелкие подзадачи, пока не решим наименьшую известную подзадачу (листовой узел). . После этого решения подзадач собираются слой за слоем посредством обратного отслеживания, чтобы построить решение исходной проблемы.

Напротив, динамическое программирование представляет собой подход «снизу вверх»: начиная с решения наименьшей подзадачи и итеративно создавая решения для более крупных подзадач, пока не будет получено решение исходной проблемы.

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

Пример кода: (динамическое программирование, начиная с наименьшей подзадачи)


# python 代码示例
def clibing_stairs_dp(n) :
    if n == 1 or n == 2 :
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3,n + 1) :
        dp[i] = dp[i-1] + dp[i- 2]
    return dp[n]


// c++ 代码示例
 
int climbingStairsDP(int n) 
{
    if (n == 1 || n == 2)
    {
        retunr n ;
    }
    vector<int> dp(n + 1, -1) ;
    dp[1] = 1 ;    
    dp[2] = 2 ;
    for (int i = 3 ; i <= n ; i++)
    {
        dp[i] = dp[i - 1] + dp[i- 2] ;
    }
    return dp[n] ;
}

Процесс выполнения (динамическое программирование):

Анализ: (динамическое программирование)

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

Основываясь на вышеизложенном, мы можем обобщить общие термины для динамических терминов:

Массив dp называется {dp table}, dp[i] представляет собой решение подзадачи, соответствующей состоянию i.
Состояние, соответствующее минимальной подзадаче (первая и вторая ступеньки), называется начальным состоянием.
Рекурсивная формула dp[i] = dp[i-1] + dp[i-2] называется уравнением состояния

Оптимизация пространства:

dp[i] относится только к dp[i-1] и dp[i-2]

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

Пример кода:


# python 代码示例
def clibing_stairs_dp_comp(n) :
    if n == 1 or n == 2 :
        return n
    a, b = 1, 2
    for _ in range(3, n + 1) :
        a, b = b , a + b
    return b


// c++ 代码示例
int climbingStairsComp(int n) 
{
    if (n == 1 || n == 2)
    {
        return n ;
    }
    int a = 1 , b = 2 ;
    for (int i = 3 ; i <= n ; i++)
    {
        int temp = b ;
        b = a + b ;
        a = temp ;
    }
    return b ;
}

Анализ:

Пространство, занимаемое массивом dp, опускается, а сложность пространства снижается с O(n) до O(1).

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

Обмен технологиями