给出3套动态规划的算法题，并给出完整的讲解和java代码

动态规划是一种常用的算法思想，常用于解决优化问题。下面我将给出三个动态规划的算法题，并提供完整的讲解和Java代码。

1. 最长公共子序列

给定两个字符串S和T，求它们的最长公共子序列（LCS）。

解法：使用动态规划算法，定义一个二维数组dp[i][j]表示S的前i个字符和T的前j个字符的LCS长度。则有：

- 若S[i]==T[j]，则dp[i][j]=dp[i-1][j-1]+1；
- 若S[i]!=T[j]，则dp[i][j]=max(dp[i-1][j], dp[i][j-1])。

最终结果为dp[S.length()][T.length()]。

Java代码：

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++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i-1) == text2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

2. 矩阵链乘法

给定n个矩阵{A1,A2,…,An}，其中Ai的规模为pi-1×pi（i=1,2,…,n），求完全括号化方案，使得计算矩阵链的乘积所需的标量乘法次数最少。

解法：使用动态规划算法，定义一个二维数组dp[i][j]表示从第i个矩阵到第j个矩阵的最小标量乘法次数。则有：

- 当i=j时，dp[i][j]=0；
- 当i<j时，dp[i][j]=min{dp[i][k]+dp[k+1][j]+pi-1×pk×pj}，其中i<=k<j。

最终结果为dp[1][n]。

Java代码：

public int matrixChainOrder(int[] p) {
    int n = p.length - 1;
    int[][] dp = new int[n+1][n+1];
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n-len+1; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]);
            }
        }
    }
    return dp[1][n];
}

3. 背包问题

有一个容量为W的背包和n个物品，第i个物品的重量为wi，价值为vi。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

解法：使用动态规划算法，定义一个二维数组dp[i][j]表示前i个物品装入容量为j的背包可获得的最大价值。则有：

- 当i=0或j=0时，dp[i][j]=0；
- 当i>0且j>=wi时，dp[i][j]=max(dp[i-1][j], dp[i-1][j-wi]+vi)；
- 当i>0且j<wi时，dp[i][j]=dp[i-1][j]。

最终结果为dp[n][W]。

Java代码：

public int knapsack(int W, int[] wt, int[] val, int n) {
    int[][] dp = new int[n+1][W+1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (j >= wt[i-1]) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][W];
}