【LeetCode】Sama的个人记录

【Q120】(md) 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。

例如，给定三角形：

[
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

>>> 先明确，局部最优不一定是全局最优。所以"自上而下一直选最小值(最优解)走一条路径"这种思路是错误的
>>> 你需要列举出所有情况————这不可避免

class Solution {
	/*
	【动态规划 + 降维优化】
	
	核心思路：自底向上进行DP
	动态转移方程：dp[i][j] = Math.min(dp[i][j], dp[i][j + 1]) + triangle.get(i).get(j);
	
	其实，这个过程直接在一维数组进行原地操作就可以了：
	降维优化的动态转移方程：dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
	*/
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        int[] dp = new int[len];

        for(int i = len - 1; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                dp[j] = Math.min(dp[j], (j + 1 <= len - 1 ? dp[j + 1] : 0)) + triangle.get(i).get(j);
            }
        }

        return dp[0];
    }
}

>>> 本题【递归回溯】会超时
>>> DP和递归回溯的思想都是"从底层开始构建"。但是从昨天起骑士救公主和今天的三角形路径可以看出，这个"底层"的含义似乎不同:
>>> 递归是正向思维的构建，是对过程的复现；DP则更倾向于解决问题而不是重演问题（不管正向逆向，能解决问题就行）

【Q96】(md) 不同的二叉搜索树

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:
输入: 3
输出: 5

class Solution {
    /*
    【动态规划】

    很好理解，也很优美。
    dp的值为节点个数为下标时，二叉线索树的个数
    以dp[4]为例，说明一下动态转移方程：
    有4个节点时，根节点可以是1或2或3或4：
            当根节点为1时，左树节点数为0，右树节点数为3
            当根节点为2时，左树节点数为1，右树节点数为2
            当根节点为3时，左树节点数为2，右树节点数为1
            当根节点为4时，左树节点数为3，右树节点数为0
     因此dp[4] = dp[0]*dp[3] + dp[1]*dp[2] + dp[2]*dp[1] + dp[3]*dp[0]
     
     */
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++){
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
}

【Q97】(hd) 交错字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:
输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” 输出: true
示例 2:
输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc” 输出: false

class Solution {
    /**
     *【动态规划】
     * dp[i][j]的值的含义是：s1的前j个字母与s2的前i个字母能否匹配s3的前i+j个字母
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s2.length();
        int n = s1.length();
        int k = s3.length();

        if(m + n != k){         // 当s1与s2的长度之和不等于s3的长度时，必然为false
            return false;       // 这个判定不仅是一个优化，更是因为，保证下面s3.charAt(i + j - 1)不会越界
        }

        boolean[][] dp = new boolean[m + 1][n + 1];

        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                if(i == 0 && j == 0){
                    dp[i][j] = true;        // dp[0][0]处特判
                    continue;
                }
                char c = s3.charAt(i + j - 1);
                dp[i][j] = (i - 1 >= 0 ?(dp[i - 1][j] && c == s2.charAt(i - 1)) : false) || (j - 1 >= 0 ? (dp[i][j - 1] && c == s1.charAt(j - 1)) : false);
            }
        }

        return dp[m][n];
    }
}

>>> 还可以进行【滚动数据】进行压缩
>>> 因为这里数组的第 i 行只和第 i−1 行相关，所以我们可以用滚动数组优化这个动态规划，这样空间复杂度可以变成 O(n)
>>> 直接将上面的第一维删掉就可以
>>> dp[j] = (i - 1 >= 0 ?(dp[j] && c == s2.charAt(i - 1)) : false) || (j - 1 >= 0 ? (dp[j - 1] && c == s1.charAt(j - 1)) : false);
>
>>> 1.滚动数组优化之后，其dp的含义变得难以捉摸，因此这种压缩优化是在写出dp[][]代码之后再考虑的
>>> 2.虽然dp[][]的空间被压缩为dp[]，但时间复杂度丝毫不变————滚动数组只不过是在一种"原地操作"罢了