当前位置：首页 > article >正文

Leetcode Java学习记录——动态规划基础_2

article 2025/2/26 6:21:49

要理解复杂逻辑的关键

分治出子问题
dp方程
合并子问题的解
自底向上递推

最长公共子序列

两个字符串的变化问题，常可以转化成二维数组。

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length() , n =text2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i<=m ; i++){
            char c1 = text1.charAt(i-1);
            for(int j=1 ; j <= n; j++){
                char c2 = text2.charAt(j-1);
                if ( c1 == c2 ){
                    // dp[i][j] = 1 + Math.max(dp[i-1][j] , dp[i][j-1]);
                    dp[i][j] = 1 + dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}

三角形最小路径和

题目

120.给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

代码细节

List 要用.size()
int[] 要用length
Arrays.fill(cur,1); 可以用来操作 int[] cur.
int[]默认新建出来都是0.
Integer 新建出来则是null

解答

下面的代码仍有一处问题，你看得出来吗？

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
    	//注意初始化写法
        // int[] cur = new int[triangle.length];
        //int[] cur = triangle[triangle.size() - 1];
        int[] cur = new int[triangle.size()+1];
        
        // 注意边界写成哪一行
        // for(int i = triangle.size()-2; i>=0; i--)
        for(int i = triangle.size()-1 ; i>=0; i--){
            for(int j = triangle.get(i).size()-1; j>=0 ; j--){
                 cur[j] = Math.min(cur[j],cur[j+1]) + triangle.get(i).get(j);
            }
        }
        return cur[0];
    }
}

正确代码为：

   public int minimumTotal(List<List<Integer>> triangle) {
        int[] cur = new int[triangle.size()+1];
        // 注意边界写成哪一行
        for(int i = triangle.size()-1 ; i>=0; i--){
            for(int j = 0; j<triangle.get(i).size() ; j++){
                cur[j] = Math.min(cur[j],cur[j+1]) + triangle.get(i).get(j);
            }
            // for(int j = triangle.get(i).size()-1; j>=0 ; j--){
            //     cur[j] = Math.min(cur[j],cur[j+1]) + triangle.get(i).get(j);
            // }
        }
        return cur[0];
    }