动态规划的本质是以空间换时间: 把一个问题划分成许多子问题, 如果这些子问题会被计算很多次, 那就把它们的计算结果存储起来以节省计算时间比如斐波那契数列的公式
F(n) = F(n-1) + F(n-2)
, 其中 F(n-1) 和 F(n-2) 的结果会被计算很多次, 所以可以使用一个数组存储对应的结果 a[i] = F(i)
动态规划问题求解的一般步骤是先划分子问题找出状态转移方程找出边界条件然后计算在最长公共子字符串这个问题中, 子问题可以如此划分:
令 L(i,j) 表示字符串 s1[0..i] 和字符串 s2[0..j] 的以 s1[i] 和 s2[j] 结尾的最长公共子字符串的长度, 则
1. 当 s1[i] == s2[j] 时, L(i,j) = L(i-1,j-1)+1;
2. 当 s1[i] != s2[j] 时, L(i,j) = 0
计算出所有的
L(i,j), 其中 0<=i<s1.length,0<=j<s2.length
, 然后遍历 L 矩阵找出最大值即可
代码如下, 其中找出最大值这一步和计算矩阵结果这一步可以合并, 以减少循环次数:
- public static int f(String s1, String s2) {
- int m = s1.length();
- int n = s2.length();
- char[] c1 = s1.toCharArray();
- char[] c2 = s2.toCharArray();
- int[][] dp = new int[m][n];
- // 初始化 dp 的第一行和第一列
- for (int i = 0; i < m; i++) {
- if (c1[i] == c2[0])
- dp[i][0] = 1;
- }
- for (int i = 0; i < n; i++) {
- if (c1[0] == c2[i])
- dp[0][i] = 1;
- }
- // 生成状态转移矩阵并找出最大值
- int max = 0;
- for (int i = 1; i < m; i++) {
- for (int j = 1; j < n; j++) {
- if (c1[i] == c2[j]) {
- int result = dp[i - 1][j - 1] + 1;
- dp[i][j] = result;
- max = max < result ? result : max;
- }
- }
- }
- return max;
- }
可以看到, 在计算矩阵 dp 的第 i 行时, 只用到了 dp 的第 i-1 行, 所以只使用两行数组就可以计算出矩阵的值, 这样可以减少内存消耗代码如下:
- public static int fLessMem(String s1, String s2) {
- int m = s1.length();
- int n = s2.length();
- char[] c1 = s1.toCharArray();
- char[] c2 = s2.toCharArray();
- int[][] dp = new int[2][n];
- for (int i = 0; i < n; i++) {
- if (c1[0] == c2[i]) {
- dp[1][i] = 1;
- }
- }
- int max = 0;
- int cur = 1; // 指明 dp 矩阵的哪一行是正在计算的行
- int data = 0; // 指明 dp 矩阵的行是缓存的行
- for (int i = 1; i < m; i++) {
- // 更新缓存行的第一个元素
- // 由于现在计算的是第 i 行, 所以 data 行对应的是第 i-1 行的元素
- dp[data][0] = c1[i - 1] == c2[0] ? 1 : 0;
- for (int j = 1; j < n; j++) {
- if (c1[i] == c2[j]) {
- int result = dp[data][j - 1] + 1;
- dp[cur][j] = result;
- max = max < result ? result : max;
- }
- }
- // 交换正在计算的行和缓存的数据行
- cur ^= data;
- data ^= cur;
- cur ^= data;
- }
- return max;
- }
来源: http://blog.csdn.net/Q_AN1314/article/details/79656541