动态规划（四）

上一篇文章写了在动态规划中，最长子序列这一类型的题目。这一次我想要来讲一讲关于杨辉三角这一类型的题目，在LeetCode上这一类型的题目有：
第119题 杨辉三角2 https://leetcode-cn.com/problems/pascals-triangle-ii/
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
输入: 3
输出: [1,3,3,1]
从示例就可以看出：第 k 行，是索引为 k 的行数，即 k+1 行。
其实这道题的状态转移方程是挺好找的，就是根据杨辉三角的特性即可得到：dp[i][j] = dp[i-1][j-1]+dp[i-1][j]，然后我们还可以用滚动数组来把空间复杂度降低到O(k)。注意，要复用数组，我们就可以自然而然的想到，可以从后往前更新。因此代码如下：

public static List<Integer> getRow(int rowIndex) {
        int[] dp = new int[rowIndex + 1];
        for (int i = 0; i <= rowIndex; i++) {
            for (int j = i; j >= 0; j--) {
                dp[j] = j == 0 || j == i ? 1 : dp[j - 1] + dp[j];
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < dp.length; i++) {
            list.add(dp[i]);
        }
        return list;
    }

同类型的题目还有第120题 三角形最小路径和 https://leetcode-cn.com/problems/triangle/
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
这道题的关键就是要想明白，到达当前点的最小路径等于它自己加上到达上面两个点的最小距离中的较小值。但这里还要除去特殊情况，就是分别在两边的点。到达他们的最小距离就等于到达上面那个点的最小距离加上自身。ok，代码如下：

public static int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i - 1][j - 1], dp[i - 1][j]);
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, dp[n - 1][i]);
        }
        return ans;
    }

在此基础上，我们还可以使用滚动数组来降低空间复杂度，代码如下：

public static int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n + 1];
        dp[0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            //每行最后一个
            dp[i] = dp[i - 1] + triangle.get(i).get(i);
            for (int j = i - 1; j > 0; j--) {
                //从后往前
                dp[j] = Math.min(dp[j - 1], dp[j]) + triangle.get(i).get(j);
            }
            //每行第一个，给dp[0]赋值下一轮的第一个
            dp[0] += triangle.get(i).get(0);

        }
        int ans = dp[0];
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, dp[i]);
        }
        return ans;
    }

好了，以上就是我对于动态规划中杨辉三角这类题目的一些理解，本人才疏学浅，如有不对，还望批评指正。