```java
package net.zhaoxuyang.common.algorithm.dp;
/**
* 最長公共子序列
*
* @author zhaoxuyang
*/
public class LastestCommonSequence {
public static void main(String[] args) {
String x = "ABCBDAB";
String y = "BDCABA";
int m = x.length();
int n = y.length();
int[][] c = new int[m + 1][n + 1];
int[][] b = new int[m + 1][n + 1];
lscLength(x.toCharArray(), y.toCharArray(), c, b);
// for (int i = 0; i <= x.length(); i++) {
// for (int j = 0; j <= y.length(); j++) {
// System.out.print(b[i][j]+" ");
// }
// System.out.println();
// }
lcs(x.length(), y.length(), x.toCharArray(), b);
}
/**
* <pre>
* ------------------------------------------------------------
* = 0 i=0 || j=0
* c[i][j] = c[i-1][j-1]+1 i,j>0 && x[i]=y[j]
* = max(c[i][j-1],c[i-1][j]) i,j>0 && x[i]!=y[j]
*
* b[i][j]=1 表示c[i][j]由c[i-1][j-1]+1 得到
* b[i][j]=2 表示c[i][j]由c[i][j-1] 得到
* b[i][j]=3 表示c[i][j]由c[i-1][j] 得到
* ------------------------------------------------------------
* i行j列,初始時c[i][0]=0,c[0][j]=0
* B D C A B A
* 0 0 0 0 0 0 0
* A 0
* B 0
* C 0
* B 0
* D 0
* A 0
* B 0
* ------------------------------------------------------------
* </pre>
*
* @param x X序列
* @param y Y序列
* @param c 存入最優值
* @param b 存入最優值的來源
*/
private static void lscLength(char[] x, char[] y, int[][] c, int[][] b) {
for (int i = 1; i <= x.length; i++) {
for (int j = 1; j <= y.length; j++) {
if (x[i - 1] == y[j - 1]) {
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
} else if (c[i][j - 1] > c[i - 1][j]) {
c[i][j] = c[i][j - 1];
b[i][j] = 2;
} else {
c[i][j] = c[i - 1][j];
b[i][j] = 3;
}
}
}
}
/**
* 根據記錄下的信息構造最優解
*/
private static void lcs(int i, int j, char[] x, int[][] b) {
if (i == 0 || j == 0) {
return;
}
switch (b[i][j]) {
case 1:
lcs(i - 1, j - 1, x, b);
visit(x[i - 1]);
break;
case 2:
lcs(i, j - 1, x, b);
break;
default:
lcs(i - 1, j, x, b);
break;
}
}
/**
* 如何處理最優解,例如打印,或者添加到StringBuilder中
* @param c
*/
private static void visit(char c) {
System.out.print(c);
}
}
```
- 1 設計接口
- 1.1 容器接口Container
- 1.2 背包接口Bag
- 1.3 棧接口Stack
- 1.4 隊列接口Queue
- 1.5 Union-Find算法接口UF
- 2 實現接口
- 2.1 結點類Node
- 2.2 數組迭代器ArrayIterator
- 2.3 鏈表迭代器ListIterator
- 2.4 背包(Bag)的實現
- 2.4.1 能動態調整數組大小的Bag
- 2.4.2 鏈式Bag的實現
- 2.5 棧(Stack)的實現
- 2.5.1 能動態調整數組大小的Stack
- 2.5.2 鏈式Stack的實現
- 2.6 隊列(Queue)的實現
- 2.6.1 能動態調整數組大小的Queue
- 2.6.2 鏈式Queue的實現
- 2.7 Union-Find算法的實現
- 2.7.1 DefaultUF
- 2.7.2 QuickFindUF
- 2.7.3 QuickUnionUF
- 2.7.4 WeightedQuickUnionUF
- 2.8 測試
- 2.8.1 測試Stack
- 2.8.2 測試Union-Find
- 3 排序算法
- 3.1 定義排序工具的類結構
- 3.2 選擇排序
- 3.3 插入排序
- 3.4 希爾排序
- 3.5 歸并排序
- 3.5.1 歸并排序的合并方法
- 3.5.2 自頂向下的歸并排序
- 3.5.3 自底向上的歸并排序
- 3.6 快速排序
- 3.6.1 常規快速排序
- 3.6.2 排序前先洗牌
- 3.6.3 快速排序的改進方法-小數據量轉成插入排序
- 3.6.4 快速排序的改進方法-三向切分
- 3.7 堆排序
- 3.8 最終的排序工具
- 4 搜索
- 4.1 二分搜索(binarySearch)
- 4.2 優先隊列(MaxPriorityQueue)
- 4.3 二叉查找樹(BST)
- 4.4 紅黑二叉查找樹(RedBlackBST)
- 4.5 B-樹(BTree)
- 5 圖
- 5.1 無向圖(Graph)
- 5.2 有向圖(Digraph)
- 6 貪心
- Dijkstra算法-單元最短路徑
- 7 動態規劃
- 7.1 最長公共子序列問題
- 7.2 0-1背包問題
- 7.3 加工順序問題
- 8 搜索法
- 8.1 圖的著色問題
- 8.2 深度優先搜索
- 8.3 回溯法
- 8.3.1 回溯法的算法框架
- 8.3.2 子集樹
- 8.3.3 排列樹
- 8.3.4 滿m叉樹(組合樹)
- 8.4 廣度優先搜索
- 8.5 分支限界法
- 9 隨機化算法
- 9.1 數值隨機化算法
- 9.2 蒙特卡羅算法
- 9.3 拉斯維加斯算法
- 9.4 舍伍德算法
- 10 數論算法
- 10.1 Stein求最大公約數
- 10.2 矩陣求斐波那切數列
- LeetCode刷題筆記