认识动态规划

动态规划的核心思想是将复杂问题分解成小的、易于解决的子问题，并找到这些子问题之间的递推关系。每个子问题只解决一次，并将其解保存起来，如果再遇到相同的子问题，只是简单地查表取出已计算的结果。
动态规划的过程通常分为四个阶段：

定义子问题
实现需要反复执行解决的子问题部分
识别并求解出基本子问题
通过递推关系，自底向上地将子问题的解组合起来，形成原问题的解

爬楼梯

力扣题目链接
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

dp 数组的含义是爬到第 i 级台阶有 dp[i] 种爬法

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

不同路径

力扣题目链接
一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？

多维动态规划，状态转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp 数组首行首列值全为 1，因为抵达首行首列每个元素能走的路径只有 1 种

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

最小路径和

力扣题目链接
给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

多维动态规划，首行首列的 dp 数组对应值是前一行（前一列）的 dp 值与当前 grid 值之和

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < cols; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][cols - 1];
    }
}

完全平方数

力扣题目链接
给你一个整数 n，返回和为 n 的完全平方数的最少数量。

动态规划，转移方程是 dp[i] = 最小的 dp[i - j * j] + 1

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = min + 1;
        }
        return dp[n];
    }
}