Практики динамического программирования: проблемы Leetcode в JavaScript

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

Число Фибоначчи

Есть несколько вариантов решения этой проблемы. Мы знакомы с первой рекурсией: мы рекурсивно вычисляем fib(n-1) и fib(n-2), пока не встретимся с граничным случаем. Однако рекурсивное вычисление числа Фибоначчи приведет к O(2^N) времени выполнения. Применяя динамическое программирование, мы можем уменьшить его до O(N), создав массив для запоминания предыдущего результата.

Например, если задано N 8. Мы создадим массив для хранения числа Фибоначчи в range[2, N].

original dp: [0, 1]
when i = 2, fib(2) = dp[2–1] + dp[2–2], dp = [0,1,1];
when i = 3, fib(3) = dp[3–1] + dp[3–2], dp = [0,1,1,2];
when i = 4, fib(4) = dp[4–1] + dp[4–2], dp = [0,1,1,2,3];
when i = 5, fib(5) = dp[5–1] + dp[5–2], dp = [0,1,1,2,3,5];
when i = 6, fib(6) = dp[6–1] + dp[6–2], dp = [0,1,1,2,3,5,8];
when i = 7, fib(7) = dp[7–1] + dp[7–2], dp = [[0,1,1,2,3,5,8,13];
when i = 8, fib(8) = dp[8–1] + dp[8–2], dp = [[0,1,1,2,3,5,8,13,21];
fib(8) = 21

Решение на JS:

var fib = function(N) {
    if (N === 0) {
        return 0
    } else if (N == 1) {
        return 1
    }
    var dp = [0, 1]
    for (var i = 2; i <= N; i++) {
        var number = dp[i - 1] + dp[i - 2]
        dp.push(number)
    }
    return dp[dp.length - 1]
};

Самая длинная возрастающая подпоследовательность

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

array = [10,9,2,5,3,7,101,18]
dp = [1,1,1,2,2,3,4,4]
longest increasing subsequence = 4

Код JS:

var lengthOfLIS = function(nums) {
    if (!nums || nums.length === 0) {
        return 0
    }
    
    if (nums.length === 1) {
        return 1
    }
    
    var dp = new Array(nums.length).fill(0)
    var max = 0
    
    for (var i = 0; i < nums.length; i++) {
        dp[i] = 1
        for (var j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1
            }
        }
        max = Math.max(max, dp[i])
    }
    console.log(dp)
    return max
};

Минимальная сумма пути

Подобно массиву, матрица также может хранить предыдущие результаты. Например, мы можем matrix[i][j] хранить минимальную сумму пути в текущей позиции.

matrix = [
          [1,3,1],
          [1,5,1],
          [4,2,1]]
    dp = [
          [1,4,5],
          [2,7,6],
          [6,8,7]]    minimum path = 7

Код JS:

var minPathSum = function(grid) {
    if (!grid || grid.length === 0 || grid[0].length === 0) {
        return 0;
    }
    var m = grid.length
    var n = grid[0].length
    for (var i = 0; i < grid.length; i++) {
        for (var j = 0; j < grid[i].length; j++) {
            if (i === 0 && j === 0) {
                grid[i][j] *= 1
            } else if (i === 0 && j !== 0) {
                grid[i][j] += grid[i][j - 1]
            } else if(i !== 0 && j === 0) {
                grid[i][j] += grid[i - 1][j]
            } else {
                grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j])
            }
        }
    }
    return grid[m - 1][n - 1]
};