动态规划
把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划
算法应用
最长公共子序列问题
提供给你两个字符串，求出最长的公共字符串是多少位，不要求连续
/**
* 动态规划
* 最长公共子序列LCS
* 2017年9月9日 下午4:39:53
*
*/
public class LCS {
public int findLCS(String A, String B) {
// A串长度
int n = A.length();
// B串长度
int m = B.length();
// A串字符数组
char[] a = A.toCharArray();
// B串字符数组
char[] b = B.toCharArray();
// 二维数组
// A为行
// B为列
int[][] dp = new int[n][m];
// 遍历比对A串每一个字母与B串第一个字母
// A串为行
// 遍历行
for (int i = 0; i < n; i++) {
// A串每个字母与B串第一个字母进行比对
if (a[i] == b[0]) {
// 如果A串的字母与B串的第一个字母相等
// 则这行第一列赋值为1
dp[i][0] = 1;
// 将这行下面所有行赋值为1
// 表示从该位置开始至后面都有一个公共字符串
// 比如下面这个串，android从r开始的字符串都与random有一个公共子序列r
// android
///// random
for (int j = i + 1; j < n; j++) {
dp[j][0] = 1;
}
// 跳出循环
break;
}
}
// 遍历比对B串的每一个字母与A串第一个字母
// B串为列
// 遍历列
for (int i = 0; i < m; i++) {// 第一行
// B串的每个字母与A串的第一个字母进行比对
if (a[0] == b[i]) {
// 如果B串的字母与A串的第一个字母相等
// 则这列第一行赋值为1
dp[0][i] = 1;
// 将这行后面所有列赋值为1
// 表示从该位置开始至后面都有一个公共字符串
for (int j = i + 1; j < m; j++) {
dp[0][j] = 1;
}
break;
}
}
// 遍历二维数组，从1开始
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
// 如果两个字母相等
if (a[i] == b[j]) {
// 则该位置等于前两个字母比对的位置+1
// 表示公共子序列的长度+1
dp[i][j] = dp[i - 1][j - 1] + 1;
// 否则
} else {
// 该位置等于 该位置的上面一行位置 与 该位置的前面一列位置 最大的值
// dp[i - 1][j]:该位置上面一行位置 表示：A串当前字符的上一个字符与B串当前字符的最长子序列长度
// dp[i][j - 1]:该位置前面一列位置 表示：A串当前字符与B串当前字符的上依噶字符的最长子序列长度
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
// 二维数组最右下角的元素表示最长子序列长度
return dp[n - 1][m - 1];
}
public static void main(String[] args) {
LCS lcs = new LCS();
int findLCS = lcs.findLCS("android", "random");
System.out.println("最长子序列长度：" + findLCS);
}
}
