动态规划的java示例代码
时间: 2023-05-25 18:01:48 浏览: 46
以下是一个使用动态规划解决“最长公共子序列”问题的Java示例代码:
```java
public class LongestCommonSubsequence {
public static void main(String[] args) {
String s1 = "ABCBDAB";
String s2 = "BDCABA";
int[][] dp = new int[s1.length()+1][s2.length()+1];
for(int i=1; i<=s1.length(); i++){
for(int j=1; j<=s2.length(); j++){
if(s1.charAt(i-1) == s2.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]);
}
}
}
System.out.println("Length of LCS: " + dp[s1.length()][s2.length()]);
}
}
```
这段代码计算了两个字符串s1和s2的最长公共子序列。它使用一个二维数组dp来保存已计算的中间结果。首先,我们将dp数组初始化为零。然后,我们逐个字符检查s1和s2中的每个字符,并确定是否匹配。如果匹配,则将dp[i][j]的值设置为dp[i-1][j-1]+1。否则,将其设置为dp[i-1][j]和dp[i][j-1]中的最大值。在完成所有计算后,dp[s1.length()][s2.length()]中包含的值就是最长公共子序列的长度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)