动态规划

爬楼梯

$dp_{i} = dp_{i - 1} + dp_{i - 2}$

function climbStairs(n: number): number {
    if (n === 1) return 1 // 特殊值
 
    let dp = [1, 2]
    for (let i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp.at(-1)
};

打家劫舍

$dp_{i} = \max (dp_{i - 1}, dp_{i - 2} + val)$

function rob(nums: number[]): number {
    if (nums.length === 1) return nums[0] // 特殊值
 
    let dp = [nums[0], Math.max(nums[0], nums[1])]
    for (let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
    }
    return dp.at(-1)
};

最小路径和

$dp_{i, j} = \min (dp_{i - 1, j}, dp_{i, j - 1})$

function minPathSum(grid: number[][]): number {
    let [row, col] = [grid.length, grid[0].length]
    let dp = grid
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (i === 0 && j === 0) continue // 特殊值
            else if (i === 0) dp[i][j] += dp[i][j - 1] // 特殊值
            else if (j === 0) dp[i][j] += dp[i - 1][j] // 特殊值
            else dp[i][j] += Math.min(dp[i][j - 1], dp[i - 1][j])
        }
    }
    return dp[row - 1][col - 1]
};

不同路径

$dp_{i, j} = dp_{i - 1, j} + dp_{i, j - 1}$

function uniquePaths(m: number, n: number): number {
    let dp = Array(m).fill(1).map(() => Array(n).fill(1)) // 特殊值
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
};

不同路径 II

$dp_{i, j} = \begin{cases} dp_{i - 1, j} + dp_{i, j - 1} & , val = 0 \\ 0 & , val = 1 \end{cases}$

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    let [row, col] = [obstacleGrid.length, obstacleGrid[0].length]
    let dp = obstacleGrid
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (dp[i][j] === 1) {
                dp[i][j] = 0 // 特殊值
            } else {
                if (i === 0 && j === 0) dp[i][j] = 1 // 特殊值
                else if (i === 0) dp[i][j] = dp[i][j - 1] // 特殊值
                else if (j === 0) dp[i][j] = dp[i - 1][j] // 特殊值
                else dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
            }
        }
    }
    return dp[row - 1][col - 1]
};

最大子数组和

$dp_{i} = \max (val, val + dp_{i - 1})$

其中 dp[i] 表示以 nums[i] 结尾的最大子数组和

function maxSubArray(nums: number[]): number {
    let dp = [nums[0]]
    for (let i = 1; i < nums.length; i++) {
        dp[i] = Math.max(nums[i], nums[i] + dp[i - 1])
    }
    return Math.max(...dp)
};

分割等和子集

$dp_{i, j} = \max (dp_{i - 1, j}, dp_{i - 1, j - w} + v)$

重量：nums[i]
价值：nums[i]
容量：sum / 2
目标：求能装的最大价值

function canPartition(nums: number[]): boolean {
    let sum = nums.reduce((a, b) => a + b)
    if (sum % 2 === 1) return false // 特殊值
 
    let cap = sum / 2
    let [row, col] = [nums.length, cap + 1]
    let dp = Array(row).fill(0).map(() => Array(col).fill(0))
 
    for (let j = 0; j < col; j++) { // 处理 dp 第一行
        let [w, v] = [nums[0], nums[0]]
        dp[0][j] = j < w ? 0 : v
    }
 
    for (let i = 1; i < row; i++) {
        for (let j = 1; j < col; j++) {
            let [w, v] = [nums[i], nums[i]]
            if (j < w) {
                dp[i][j] = dp[i - 1][j]
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v)
            }
        }
    }
    return dp[row - 1][col - 1] === cap
};