用java语言实现一个动态规划算法

动态规划算法是一种解决多阶段决策过程最优化问题的算法。这里给出一个用Java语言实现的动态规划算法，以求解最长公共子序列问题为例。

最长公共子序列问题描述：给定两个序列X和Y，求它们的最长公共子序列（LCS）。LCS是指X和Y的一个最长的序列，该序列既是X的子序列，也是Y的子序列。

算法思路：

（1）定义状态：设X={x1,x2,…,xm}，Y={y1,y2,…,yn}，LCS(X,Y)表示X和Y的LCS。令c[i][j]表示X前i个字符和Y前j个字符的LCS的长度。

（2）状态转移方程：当Xi=Yj时，c[i][j]=c[i-1][j-1]+1；当Xi≠Yj时，c[i][j]=max{c[i-1][j],c[i][j-1]}。

（3）边界：当i=0或j=0时，c[i][j]=0。

（4）最优解：c[m][n]即为X和Y的LCS的长度。

Java实现代码：

public class LCS { public static void main(String[] args) { String X = "ABCBDAB"; String Y = "BDCABA"; int[][] c = new int[X.length() + 1][Y.length() + 1]; for (int i = 1; i <= X.length(); i++) { for (int j = 1; j <= Y.length(); j++) { if (X.charAt(i - 1) == Y.charAt(j - 1)) { c[i][j] = c[i - 1][j - 1] + 1; } else { c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]); } } } System.out.println("LCS长度为：" + c[X.length()][Y.length()]); } }

输出结果：

LCS长度为：4

说明：X和Y的最长公共子序列为“BCBA”。