基础算法 - 动态规划 - 2

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1]; // 创建大小为 (m+1)x(n+1) 的二维数组
        dp[0][1] = 1; // 初始化起点前一个位置为 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][n]; // 返回到达终点 (m, n) 的路径数量
    }
}

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 第一排 和第一列特殊处理
                if (i == 1) {
                    dp[i][j] = dp[i][j - 1] + grid[i - 1][j - 1];
                } else if (j == 1) {
                    dp[i][j] = dp[i - 1][j] + grid[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();  // 获取字符串的长度
        boolean[][] dp = new boolean[len + 2][len + 2];  // 定义二维布尔数组，用于存储动态规划的状态
        
        // 初始化dp数组，全部设为true（这是多余的，实际使用中可以直接省略这一步）
        for (int i = 0; i <= len + 1; i++)
            Arrays.fill(dp[i], true);
        
        int start = -1;  // 最长回文子串的起始索引
        int end = -1;    // 最长回文子串的结束索引
        int maxLen = -1; // 最长回文子串的长度
       
        // 倒序遍历字符串
        for (int i = len; i >= 1; i--) {
            for (int j = i; j <= len; j++) {
                // 判断子串s[i-1...j-1]是否为回文串
                dp[i][j] = dp[i + 1][j - 1] && (s.charAt(i - 1) == s.charAt(j - 1));
                if (dp[i][j]) {
                    // 如果是回文串，且长度大于当前最长回文子串长度，更新start, end, 和 maxLen
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        start = i - 1;
                        end = j;
                    }
                }
            }
        }
        
        return s.substring(start, end);  // 返回最长回文子串
    }
}

class Solution {
    //定义两个边界为全局变量
    int left;
    int right;
    public String longestPalindrome(String s) {
        left = 0;
        right = 0;
        //在遍历字符时将字符串转换为字符数组操作效率更高
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length-1; i++) {
            valid(charArray,i,i);//单个字符中心开花判断
            valid(charArray,i,i+1);//两个字符中心开花
        }
        return new String(charArray,left,right-left+1);

    }
    public void valid(char[] charArray , int i ,int j){
        while (i>= 0 && j < charArray.length && charArray[i] == charArray[j]){
            i--;
            j++;
        }
        //循环结束时,判断该回文子串是否为最大
        i++;//结束时i,j已经不是回文子串的范围,所以需要将其加加
        j--;
        if (j - i > right -left){
            left = i;
            right = j;
        }
    }
}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length(); // 获取text1的长度
        int len2 = text2.length(); // 获取text2的长度
        int[][] dp = new int[len1+1][len2+1]; // 定义dp数组，dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度
        char[] charArray1 = text1.toCharArray(); // 将text1转换为字符数组
        char[] charArray2 = text2.toCharArray(); // 将text2转换为字符数组

        // 遍历text1和text2的每个字符
        for(int i=1; i<=len1; i++) {
            for(int j=1; j<=len2; j++) {
                // 如果当前字符相等，则dp[i][j]等于dp[i-1][j-1]加1
                if(charArray1[i-1] == charArray2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    // 否则，dp[i][j]等于dp[i][j-1]和dp[i-1][j]的较大值
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
            }
        }
        // 返回dp数组的最后一个元素，即最长公共子序列的长度
        return dp[len1][len2];
    }
}

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // 初始化边界条件：dp[i][0] = i 表示将 word1 的前 i 个字符删除需要 i 步
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        // 初始化边界条件：dp[0][j] = j 表示将 word2 的前 j 个字符插入需要 j 步
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }

        // 将 word1 和 word2 转换为字符数组，方便按字符处理
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();

        // 动态规划填表过程
        for (int i = 1; i <= m; i++) {
            char char1 = charArray1[i - 1];
            for (int j = 1; j <= n; j++) {
                char char2 = charArray2[j - 1];
                
                // 在word2中插入：dp[i][j-1] + 1，对应将 word1 的前 i 个字符转换为 word2 的前 j-1 个字符
                int insert_j = dp[i][j - 1] + 1;
                
                // 在word1中插入：dp[i-1][j] + 1，对应将 word1 的前 i-1 个字符转换为 word2 的前 j 个字符
                int insert_i = dp[i - 1][j] + 1;
                
                // 替换操作：dp[i-1][j-1] + 1（如果 char1 != char2），否则 dp[i-1][j-1]
                int replace = dp[i - 1][j - 1];
                if (char1 != char2) {
                    replace += 1;
                }

                // 取三者中的最小值
                dp[i][j] = Math.min(Math.min(insert_j, insert_i), replace);
            }
        }

        // 返回最终结果：将 word1 转换为 word2 所需的最小操作数
        return dp[m][n];
    }
}