Bryce1010
commented
4 years ago - [ ] fucking-algorithm [github]
- 历史文章摘要目录 [weixin]
Open Bryce1010 opened 4 years ago
Bryce1010
commented
4 years ago Bryce1010
commented
4 years ago
//数组遍历框架
void traverse(int[] arr){
for(int i=0;i<arr.length();i++)
//迭代访问arr[i]
}
//链表遍历框架
class ListNode{
int val;
ListNode next;
};
void traverse(ListNode head){
for(ListNode p=head;p!=NULL;p=p.next){
//迭代访问p.val
}
}
void traverse(ListNode head){
//递归访问head.val
traverse(head.next);
}
//二叉树遍历框架
class TreeNode{
int val;
TreeNode left,right;
};
void traverse(TreeNode root){
traverse(root.left);
traverse(root.right);
}
//N叉树遍历访问框架
class TreeNode{
int val;
TreeNode[] children;
};
void traverse(TreeNode root){
for(TreeNode child: root.children)
traverse(child);
}// 二叉树框架
void traverse(TreeNode root){
//前序遍历
traverse(root.left);
//中序遍历
traverse(root.right);
//后续遍历
}void traverse(TreeNode root) {
// root 需要做什么？在这做。
// 其他的不用 root 操心，抛给框架
traverse(root.left);
traverse(root.right);
}boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (root.val == target) return true;
return isInBST(root.left, target)
|| isInBST(root.right, target);
}进阶版:
boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (root.val == target)
return true;
if (root.val < target)
return isInBST(root.right, target);
if (root.val > target)
return isInBST(root.left, target);
// root 该做的事做完了，顺带把框架也完成了，妙
}二叉树遍历框架
void BST(TreeNode root, int target) {
if (root.val == target)
// 找到目标，做点什么
if (root.val < target)
BST(root.right, target);
if (root.val > target)
BST(root.left, target);
}在BST中插入一个数
TreeNode insertIntoBST(TreeNode* root, int val){
if(root==NULL) return new TreeNode(val);
// if(root->val==val)
// root->val=val;
if(root->val<val)
insertIntoBST(root->right,val);
if(root->val>val)
insertIntoBST((root->left,val);
return root;
}在BST中删除一个数
TreeNode deleteNode(TreeNode* root, int key){
if(root=NULL)return NULL;
if(root->val==key){
//情况1 如果root为叶子节点, 直接替换
//情况2, 如果root存在一个儿子, 直接用儿子节点替换
if(root->left==NULL)return root->right;
if(root->right==NULL)return root->left;
//情况3, 如果root有左儿子和右儿子, 那么寻找右儿子最小的点替代
TreeNode* minNode=getMin(root.right);
root-val=minNode->val;
root->right=deleteNode(root->right,minNode->val);
}
if(root->val>key)
deleteNode(root->left,key);
if(root->val<key)
deleteNode(root->right,key);
return root;
}
TreeNode* getMin(TreeNode* root){
while(root->left!=NULL)root=root->left;
return root;
}
动态规划的一般形式是求最值, 最长递增子序列, 最小编辑距离等等
求解动态规划的核心问题是 穷举
动态规划的特点:
明确状态 -> 定义dp数组/ 函数的含义 -> 明确选择 -> 明确base case
int fib(int N){
if(N<1)return 0;
vector<int>memo(N+1,0);
return helper(memo,N);
}
int hleper(vector<int>& memo, int n){
if(n==1||n==2)return 1;
if(memo[n]!=0)return memo[n];
memo[n]=helper(memo,n-1)+helper(memo,n-2);
return memo[n];
}
上面这种就叫做自顶向下的思想;
DP的解法一般是自底向上的解法:
int fib(int N){
vector<int>dp(N+1,0);
dp[1]=dp[2]=1;
for(int i=3;i<=N;++i)
dp[i]=dp[i-1]+dp[i-2];
return dp[N];
}
首先子问题是叠加的, 金额为10的情况需要考虑金额为9, 8 5 这几种情况
其次子结构都是寻找最优值, 而且子问题间都是相互独立的;
最后如何列出状态转移方程:
第一, 确定状态, dp[n]表示金额为n的时候, 最少需要的硬币数量;
第二, 做选择, 对所有`面额的硬币都可以做选择;
最后确定base condition;
def coinChange(coins, amount):
def dp(n):
for coin in coins:
res=min(res, dp(n-coin)+1)
return res
return dp(amount) 确定base condition; n=0的时候dp[n]=0, dp[<0]的时候, 返回-1无解;
def coinChange(coins, amount):
def dp(n):
if(n==0): return 1
if(n<0): return -1
res=float('INF')
for coin in coins:
res=min(res, dp(n-coin)+1)
return res
return dp(amount) 通过添加备忘录, 消除子问题
def coinChange(coins, amount):
memo=dict()
def dp(n):
for n in memo: return memo[n]
if(n==0): return 1
if(n<0): return -1
res=float('INF')
for coin in coins:
res=min(res, dp(n-coin)+1)
memo[n]=res if res!=float('INF') else -1
return memo[n]
return dp(amount)dp数组的迭代解法
int coinChange(vector<int>& coins, int amount){
vector<int>dp(amount+1, amount+1);
dp[0]=0;
for(int i=0;i<dp.size();i++){
for(int coin:coins){
if(i-coin<0)continue;
dp[i]=min(dp[i],dp[i-coin]+1);
}
}
return dp[amount]==amount+1?-1:dp[amount];
}解决一个回溯问题, 实际上就是一个决策树的遍历过程.
思考三个问题:
回溯算法的框架:
result=[]
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择核心就在于for循环里面的递归 , 在递归之前调用之前 做选择, 在递归调用之后 撤销选择
回溯算法== 决策树
遍历一棵决策树的算法:
void traverse(TreeNode root){
for(TreeNode child: root.children)
traverse(child);
}前序遍历的代码在进入某一个节点之前的那个时间点执行, 后序遍历代码在离开某一个节点之后的那个时间点执行.
回溯算法的核心框架:
for 选择 in 选择列表:
# 做选择
将该选择从选择列表移除
路径.add(选择)
backtrack(路径, 选择列表)
# 撤销选择
路径.remove(选择)
将该选择从新添加到选择列表
// N皇后问题
vector<vector<string>>res;
vector<vector<string>>solveNQueens(int n){
vector<string> board(n, string(n,'.'));
backtrack(board,0);
return res;
}
void backtrack(vector<string>& board, int row){
//触发结束条件
if(row==board.size()){
res.push_back(board);
return;
}
//做选择
for(int col=0;col<board[row].size();++col){
// 排除不合法
if(!isValid(board,row, col)){
continue;
}
board[row][col]='Q';
backtrack(board, row+1);
board[row][col]='.';
}
}
// N皇后随机解
bool backtrack(vector<string>& board, int row){
//触发结束条件
if(row==board.size()){
res.push_back(board);
retrurn true;
}
...
for(int col=0;col<n;col++){
...
board[row][col]='Q';
if(backtrack(board,row+1))
return true;
board[row][col]='.';
}
return false;
}
左闭右开
[l,r）
int l=0,r=n;
while(l<r)
{
r=middle;
l=middle+1;
}左闭右闭
[l,r]
int l=0,r=n-1;
while(l<=r)
{
r=middle-1;
l=middle+1;
}左开右开
(l,r)
int l=-1,r=n;
while(l+1!=r)
{
r=middle;
l=middle;
}二分模板 (求非下降序列的首次首次出现的位置)
int binary(int array[],int n,int target)
{
int left,right,middle;
left=-1,right=n;
while(left+1!=right){
middle=left+(right-left)/2;
if(array[middle]>=target){
right=middle;
}else{
left=middle;
}
}
if(right==n||array[right]!=target)
return -1;
return right;
}Matrix quickPower(Matrix A, int k){
Matrix result=I;
while(k>0)
{
if(k%1==1)result=result*A;
k=k/2;
result=result*result;
}
return result;
}我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
unordered_map 就是哈希表（字典），它的一个方法 count(key) 相当于 containsKey(key) 可以判断键 key 是否存在。
上述过程伪代码:
string s, t;
// 在 s 中寻找 t 的「最小覆盖子串」
int left = 0, right = 0;
string res = s;
while(right < s.size()) {
window.add(s[right]);
right++;
// 如果符合要求，移动 left 缩小窗口
while (window 符合要求) {
// 如果这个窗口的子串更短，则更新 res
res = minLen(res, window);
window.remove(s[left]);
left++;
}
}
return res;完整代码如下:
string minWindow(string s, string t) {
// 记录最短子串的开始位置和长度
int start = 0, minLen = INT_MAX;
int left = 0, right = 0;
unordered_map<char, int> window;
unordered_map<char, int> needs;
for (char c : t) needs[c]++;
int match = 0;
while (right < s.size()) {
char c1 = s[right];
if (needs.count(c1)) {
window[c1]++;
if (window[c1] == needs[c1])
match++;
}
right++;
while (match == needs.size()) {
if (right - left < minLen) {
// 更新最小子串的位置和长度
start = left;
minLen = right - left;
}
char c2 = s[left];
if (needs.count(c2)) {
window[c2]--;
if (window[c2] < needs[c2])
match--;
}
left++;
}
}
return minLen == INT_MAX ?
"" : s.substr(start, minLen);
}
string s,t;
unordered_set<char, set>needs;
unordered_set<char, set>window;
vector<int>res;
int match=0;
int left=0,right=0;
while(right<s.size()){
char c1=s[right];
if(needs.count(c1)){
window[c1]++;
if(window[c1]==needs[c1])
match++;
}
right++;
while(match==needs.size()){
if(right-left==t.size()){
res.push_back(left);
}
char c2=s[left];
if(needs.count(c2)){
window[c2]--;
if(window[c2]<needs[c2])
match--;
}
left++;
}
return res;
}
int left=0,right=0;
unordered_set<char, int> wondow;
while(right<s.size()){
char c1=s[right];
window[c1]++;
right++;
//如果window中出现超过2个相同字符
while(window[c1]>1){
char c2=s[left];
window[c2]--;
left++;
}
res=max(res,right-left);
}
return res;
滑动窗口 模板
int left = 0, right = 0;
while (right < s.size()) {
window.add(s[right]);
right++;
while (valid) {
window.remove(s[left]);
left++;
}
}符合最优子结构：可以从子问题的最优结果推出更大规模问题的最优结果
让你算每个班的最优成绩就是子问题，你知道所有子问题的答案后，就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。
int maxVal(TreeNode root) {
if (root == null)
return -1;
int left = maxVal(root.left);
int right = maxVal(root.right);
return max(root.val, left, right);
}但反过来，最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的
正向遍历
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
// 计算 dp[i][j]反向遍历
for (int i = m - 1; i >= 0; i--)
for (int j = n - 1; j >= 0; j--)
// 计算 dp[i][j]斜向遍历
// 斜着遍历数组
for (int l = 2; l <= n; l++) {
for (int i = 0; i <= n - l; i++) {
int j = l + i - 1;
// 计算 dp[i][j]
}1、遍历的过程中，所需的状态必须是已经计算出来的.
2、遍历的终点必须是存储结果的那个位置。
Bryce1010
commented
4 years ago 
动态规划的核心设计思想是数学归纳法。
dp[i]表示以nums[i]这个数结尾的最长上升子序列的长度;
那么我们的最终结果就是求dp[i]的最大值;
int res=0;
for(int i=0;i<n;++i){
ans=max(ans,dp[i]);
}
return res;
当我们知道dp[1-4]的结果, 那么怎么求dp[5]的结果呢?
nums[5]=3, 那么寻找nums[1-4]中小于等于3的值, 然后加1取最大值; 伪代码如下:
for(int j=0;j<index;++j){
if(nums[j]<=nums[index]){
dp[index]=max(dp[index],dp[j]+1);
}
}
那么对于所有的值, 伪代码如下:
memset(dp,1,sizeof(dp));
for(int index=0;i<n;++i){
for(int j = 0;j<index;++j){
if(nums[j]<=nums[index]){
dp[index]=max(dp[index], dp[j]+1);
}
}
}
int res=0;
for(int i=0;i<n;++i)
res=max(res,dp[i]);那么此题的动态规划法解法就完成了, 时间复杂度为O(n^2);
首先明确 dp 数组所存数据的含义。这步很重要，如果不得当或者不够清晰，会阻碍之后的步骤。
然后根据 dp 数组的定义，运用数学归纳法的思想，假设 $dp[0...i-1]$ 都已知，想办法求出 $dp[i]$，一旦这一步完成，整个题目基本就解决了。
但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。
最后想一想问题的 base case 是什么，以此来初始化 dp 数组，以保证算法正确运行。
最长递增子序列和一种叫做 patience game 的纸牌游戏有关，甚至有一种排序方法就叫做 patience sorting（耐心排序）。 最后牌堆的数量就是最长上升子序列的长度.
public int lengthOfLIS(int[] nums) {
int[] top = new int[nums.length];
// 牌堆数初始化为 0
int piles = 0;
for (int i = 0; i < nums.length; i++) {
// 要处理的扑克牌
int poker = nums[i];
/***** 搜索左侧边界的二分查找 *****/
int left = 0, right = piles;
while (left < right) {
int mid = (left + right) / 2;
if (top[mid] > poker) {
right = mid;
} else if (top[mid] < poker) {
left = mid + 1;
} else {
right = mid;
}
}
/*********************************/
// 没找到合适的牌堆，新建一堆
if (left == piles) piles++;
// 把这张牌放到牌堆顶
top[left] = poker;
}
// 牌堆数就是 LIS 长度
return piles;
} int dp(int i,int j){ if(i==-1)return i+1; if(j==-1)return j+1; if(s1[i]==s2[j]) return dp(i-1,j-1); else{ return min( dp(i-1,j-1), dp(i-1,j), dp(i,j-1) )+1; } return dp(s1.length()-1,s2.length()-1); }
- 带备忘录的递归解法
```python
def minDistance(s1, s2) -> int:
memo = dict() # 备忘录
def dp(i, j):
if (i, j) in memo:
return memo[(i, j)]
...
if s1[i] == s2[j]:
memo[(i, j)] = ...
else:
memo[(i, j)] = ...
return memo[(i, j)]
return dp(len(s1) - 1, len(s2) - 1)
#include<iostream>
using namespace std;int minValue(int a,int b,int c){ return min(a,min(b,c)); }
int minDistance(string s1,string s2){ int m=s1.length(),n=s2.length(); int[][] dp=new int[m+1][n+1]; for(int i=1;i<=m;++i){ dp[i][0]=i; } for(int j=1;j<=n;++j) dp[0][j]=j; for(int i=1;i<=m;++i){ for(int j=1;j<=n;++j){ if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]; else{ dp[i][j]=minValue(dp[i-1],dp[i-1][j],dp[i][j-1]); } } } return dp[m][n]; }
题目是这样：你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋（K 至少为 1）。现在确定这栋楼存在楼层 0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于 F 的楼层都会碎，低于 F 的楼层都不会碎）。现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层 F 呢？
「状态」很明显，就是当前拥有的鸡蛋数 K 和需要测试的楼层数 N。随着测试的进行，鸡蛋个数可能减少，楼层的搜索范围会减小，这就是状态的变化。
「选择」其实就是去选择哪层楼扔鸡蛋。回顾刚才的线性扫描和二分思路，二分查找每次选择到楼层区间的中间去扔鸡蛋，而线性扫描选择一层层向上测试。不同的选择会造成状态的转移。
# 当前状态为 K 个鸡蛋，面对 N 层楼
# 返回这个状态下的最优结果
def dp(K, N):
int res
for 1 <= i <= N:
res = min(res, 这次在第 i 层楼扔鸡蛋)
return res如果鸡蛋碎了，那么鸡蛋的个数 K 应该减一，搜索的楼层区间应该从 [1..N] 变为 [1..i-1] 共 i-1 层楼；
如果鸡蛋没碎，那么鸡蛋的个数 K 不变，搜索的楼层区间应该从 [1..N] 变为 [i+1..N] 共 N-i 层楼。
因为我们要求的是最坏情况下扔鸡蛋的次数，所以鸡蛋在第 i 层楼碎没碎，取决于那种情况的结果更大：
def dp(K, N):
for 1 <= i <= N:
# 最坏情况下的最少扔鸡蛋次数
res = min(res,
max(
dp(K - 1, i - 1), # 碎
dp(K, N - i) # 没碎
) + 1 # 在第 i 楼扔了一次
)
return res最后， 添加备忘录，消除子问题的重叠
def superEggDrop(K: int, N: int):
memo = dict()
def dp(K, N) -> int:
# base case
if K == 1: return N
if N == 0: return 0
# 避免重复计算
if (K, N) in memo:
return memo[(K, N)]
res = float('INF')
# 穷举所有可能的选择
for i in range(1, N + 1):
res = min(res,
max(
dp(K, N - i),
dp(K - 1, i - 1)
) + 1
)
# 记入备忘录
memo[(K, N)] = res
return res
return dp(K, N)如修改代码中的 for 循环为二分搜索，可以将时间复杂度降为 O(K*N*logN)；再改进动态规划解法可以进一步降为 O(KN)；使用数学方法解决，时间复杂度达到最优 O(K*logN)，空间复杂度达到 O(1)。
那么注意 dp(K - 1, i - 1) 和 dp(K, N - i) 这两个函数，其中 i 是从 1 到 N 单增的，如果我们固定 K 和 N，把这两个函数看做关于 i 的函数，前者随着 i 的增加应该也是单调递增的，而后者随着 i 的增加应该是单调递减的:
def superEggDrop(self, K: int, N: int) -> int:
memo = dict()
def dp(K, N):
if K == 1: return N
if N == 0: return 0
if (K, N) in memo:
return memo[(K, N)]
# for 1 <= i <= N:
# res = min(res,
# max(
# dp(K - 1, i - 1),
# dp(K, N - i)
# ) + 1
# )
res = float('INF')
# 用二分搜索代替线性搜索
lo, hi = 1, N
while lo <= hi:
mid = (lo + hi) // 2
broken = dp(K - 1, mid - 1) # 碎
not_broken = dp(K, N - mid) # 没碎
# res = min(max(碎，没碎) + 1)
if broken > not_broken:
hi = mid - 1
res = min(res, broken + 1)
else:
lo = mid + 1
res = min(res, not_broken + 1)
memo[(K, N)] = res
return res
return dp(K, N)这里需要重新定义DP状态
原来是 dp(k,n)-> m , 当前状态为k个鸡蛋， 面对n层楼； 返回这个状态下的最少的扔鸡蛋数。
采用dp数组表示的话为dp[k][m]-> n, 表示K个鸡蛋，可以尝试扔m次， 这时候最坏能测试的楼层数为n层。
比如dp[1][7]=7， 现在有一个鸡蛋， 尝试扔7次， 那么最坏能测试出的楼层数为7层。
int superEggDrop(int K, int N) {
int m = 0;
while (dp[K][m] < N) {
m++;
// 状态转移...
}
return m;
}状态转移方程如下：
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1那么完整的填入框架：
int superEggDrop(int K, int N) {
// m 最多不会超过 N 次（线性扫描）
int[][] dp = new int[K + 1][N + 1];
// base case:
// dp[0][..] = 0
// dp[..][0] = 0
// Java 默认初始化数组都为 0
int m = 0;
while (dp[K][m] < N) {
m++;
for (int k = 1; k <= K; k++)
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
}
return m;
}或者写成这样：
for (int m = 1; dp[K][m] < N; m++)
for (int k = 1; k <= K; k++)
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;int n = array.length;
int[] dp = new int[n];
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
dp[i] = 最值(dp[i], dp[j] + ...)
}
}在子数组 array[0..i] 中，我们要求的子序列（最长递增子序列）的长度是 dp[i]。
int n = arr.length;
int[][] dp = new dp[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j])
dp[i][j] = dp[i][j] + ...
else
dp[i][j] = 最值(...)
}
}2.1 涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义如下：
在子数组 arr1[0..i] 和子数组 arr2[0..j] 中，我们要求的子序列（最长公共子序列）长度为 dp[i][j]。
编辑距离， 公共子序列
2.2 只涉及一个字符串/数组时（比如本文要讲的最长回文子序列），dp 数组的含义如下：
在子数组 array[i..j] 中，我们要求的子序列（最长回文子序列）的长度为 dp[i][j]。
if (s[i] == s[j])
// 它俩一定在最长回文子序列中
dp[i][j] = dp[i + 1][j - 1] + 2;
else
// s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);至此，状态转移方程就写出来了，根据 dp 数组的定义，我们要求的就是 dp[0][n - 1]，也就是整个 s 的最长回文子序列的长度。
int longestPalindromeSubseq(string s){
int n=s.length();
vector<vector<int>>dp(n,vector<int>(n,0));
for(int i=n;i>=0;--i){
for(int j=i+1;j<n;++j){
if(s[i]==s[j]){
dp[i][j]=dp[i+1][j-1]+2;
}
else{
dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
}
}
}
return dp[0][n-1];
}
输入: str1 = "abcde", str2 = "ace"
输出: 3
解释: 最长公共子序列是 "ace"，它的长度是 3
第一步，一定要明确 dp 数组的含义。
dp[i][j] 的含义是：对于 s1[1..i] 和 s2[1..j]，它们的 LCS 长度是 dp[i][j]。
第二步，定义 base case。
dp[0][..] 和 dp[..][0] 都应该初始化为 0，这就是 base case。
第三步，找状态转移方程。
字符串问题的套路都差不多，权且借这道题来聊聊处理这类问题的思路。
状态转移说简单些就是做选择，比如说这个问题，是求 s1 和 s2 的最长公共子序列，不妨称这个子序列为 lcs。那么对于 s1 和 s2 中的每个字符，有什么选择？很简单，两种选择，要么在 lcs 中，要么不在。
这个「在」和「不在」就是选择，关键是，应该如何选择呢？这个需要动点脑筋：如果某个字符应该在 lcs 中，那么这个字符肯定同时存在于 s1 和 s2 中，因为 lcs 是最长公共子序列嘛。所以本题的思路是这样：
用两个指针 i 和 j 从后往前遍历 s1 和 s2，如果 s1[i]==s2[j]，那么这个字符一定在 lcs 中；否则的话，s1[i] 和 s2[j] 这两个字符至少有一个不在 lcs 中，需要丢弃一个。先看一下递归解法，比较容易理解：
递归代码如下:
def longestCommonSubsequence(str1, str2) -> int:
def dp(i, j):
# 空串的 base case
if i == -1 or j == -1:
return 0
if str1[i] == str2[j]:
# 这边找到一个 lcs 的元素，继续往前找
return dp(i - 1, j - 1) + 1
else:
# 谁能让 lcs 最长，就听谁的
return max(dp(i-1, j), dp(i, j-1))
# i 和 j 初始化为最后一个索引
return dp(len(str1)-1, len(str2)-1)改成DP Table的优化形式:
def longestCommonSubsequence(string str1, string str2):
m,n=len(str1),len(str2)
dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if(str1[i]==str2[j]):
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
return dp[m-1]对于两个字符串的动态规划问题，一般来说都是像本文一样定义 DP table，因为这样定义有一个好处，就是容易写出状态转移方程，dp[i][j] 的状态可以通过之前的状态推导出来：
Bryce1010
commented
4 years ago KMP 算法永不回退 txt 的指针 i，不走回头路（不会重复扫描 txt），而是借助 dp 数组中储存的信息把 pat 移到正确的位置继续匹配，时间复杂度只需 O(N)，用空间换时间，所以我认为它是一种动态规划算法。
设计算法框架
public class KMP {
private int[][] dp;
private String pat;
public KMP(String pat) {
this.pat = pat;
// 通过 pat 构建 dp 数组
// 需要 O(M) 时间
}
public int search(String txt) {
// 借助 dp 数组去匹配 txt
// 需要 O(N) 时间
}
}KMP kmp = new KMP("aaab");
int pos1 = kmp.search("aaacaaab"); //4
int pos2 = kmp.search("aaaaaaab"); //4后面的思想与状态机息息相关;
然后设计dp[][]数组, 记录这样的状态机;
dp[j][c]=next
0<=j<M, 代表当前状态,
0<=c<256, 表示遇到的字符(ASCII码)
0<=next<=M, 表示下一个状态
dp[4]['A']=3 表示:
当前状态时4, 遇到字符 'A',
跳转到状态3
根据上面的算法, 可以假设dp数组已经得出, 先设计search算法:
public int search(string txt){
int M=pat.length();
int N=txt.length();
int j=0;
for(int i=0;i<N;++i){
//当前状态是j, 遇到字符txt[i]
// pat应该转到什么状态
j=dp[j][txt.chatAt(i)];
//如果达到匹配条件, 则返回开头索引
if(j==M)
return i-M+1;
}
return -1;
}剩下就是怎么计算这个二维dp状态了, 初始代码应该如下:
for 0 <= j < M: # 状态
for 0 <= c < 256: # 字符
dp[j][c] = next我们采用一个影子状态, 记录上一次的前缀相同的状态:
int X # 影子状态
for 0 <= j < M:
for 0 <= c < 256:
if c == pat[j]:
# 状态推进
dp[j][c] = j + 1
else:
# 状态重启
# 委托 X 计算重启位置
dp[j][c] = dp[X][c] Search的代码如下:
public class KMP {
private int[][] dp;
private String pat;
public KMP(String pat) {
this.pat = pat;
int M = pat.length();
// dp[状态][字符] = 下个状态
dp = new int[M][256];
// base case
dp[0][pat.charAt(0)] = 1;
// 影子状态 X 初始为 0
int X = 0;
// 当前状态 j 从 1 开始
for (int j = 1; j < M; j++) {
for (int c = 0; c < 256; c++) {
if (pat.charAt(j) == c)
dp[j][c] = j + 1;
else
dp[j][c] = dp[X][c];
}
// 更新影子状态
X = dp[X][pat.charAt(j)];
}
}
public int search(String txt) {...}KMP动态规划完整(有限状态机) 代码如下:
public class KMP {
private int[][] dp;
private String pat;
public KMP(String pat) {
this.pat = pat;
int M = pat.length();
// dp[状态][字符] = 下个状态
dp = new int[M][256];
// base case
dp[0][pat.charAt(0)] = 1;
// 影子状态 X 初始为 0
int X = 0;
// 构建状态转移图（稍改的更紧凑了）
for (int j = 1; j < M; j++) {
for (int c = 0; c < 256; c++)
dp[j][c] = dp[X][c];
dp[j][pat.charAt(j)] = j + 1;
// 更新影子状态
X = dp[X][pat.charAt(j)];
}
}
public int search(String txt) {
int M = pat.length();
int N = txt.length();
// pat 的初始态为 0
int j = 0;
for (int i = 0; i < N; i++) {
// 计算 pat 的下一个状态
j = dp[j][txt.charAt(i)];
// 到达终止态，返回结果
if (j == M) return i - M + 1;
}
// 没到达终止态，匹配失败
return -1;
}
}传统的 KMP 算法是使用一个一维数组 next 记录前缀信息，而本文是使用一个二维数组 dp 以状态转移的角度解决字符匹配问题，但是空间复杂度仍然是 O(256M) = O(M)。
在 pat 匹配 txt 的过程中，只要明确了「当前处在哪个状态」和「遇到的字符是什么」这两个问题，就可以确定应该转移到哪个状态（推进或回退）。
Bryce1010
commented
4 years ago