【九章算法基础班】动态规划

Triangle

题目

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

> [
>      [2],
>     [3,4],
>    [6,5,7],
>   [4,1,8,3]
> ]
>
>

>

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

题目是说，从三角形的最上层走到最下层，每次只走到下一层的相邻元素，求从顶点走到最下层的最短路径长度。

方法1：DFS遍历

从上往下深度优先遍历搜索，记录所有情况之中最小值

public int best = Integer.MAX_VALUE;;

//sum为走到当前节点但不包含当前节点的路径和
public void dfs(List<List<Integer>> triangle,int i,int j,int sum){
  //搜索结束条件：走过了最下面一层
  int height = triangle.size();
  if(i==height){
    best = Math.min(best,sum);
    return;
  }
  dfs(triangle,i+1,j,sum+triangle.get(i).get(j));
  dfs(triangle,i+1,j+1,sum+triangle.get(i).get(j));
}

public int minimumTotal(List<List<Integer>> triangles) {
  dfs(triangles,0,0,0);
  return best;
}

时间复杂度$O(2^n)$

方法2：分治法

从最底层走到某个点[i,j]的最短路径长度可以分解为两个子问题：

1. 这个点自身的路径 长度+下一层左边节点路径长度
2. 这个点自身的路径 长度+下一层左右边节点路径长度

最终的结果需要取这两种情况的最小值。

边界条件：最下面一层的最小路径长度是1

public int divide(List<List<Integer>> triangles,int x,int y){
  //边界条件：最下面一层的路径长度是0
  int height = triangles.size();
  if(x==height)
    return 0;
  //其余点的路径长度是下一层左右两个路径长度+自身长度的最小值。
  return triangles.get(x).get(y) + Math.min(
    divide(triangles,x+1,y),
    divide(triangles,x+1,y+1)
  );
}

时间复杂度$O(2^n)$

方法3：记忆化搜索

显然上面的方法有很多重复计算的值：

/**
  [x,y]
    ↓    ↘
[x+1,y] [x+1,y+1]
   ↓      ↘ ↓       ↘
[x+2,y] [x+2,y+1] [x+2,y+2]
**/

其中[x+2,y+1]就被重复计算了两次。

可以将这些多次重复计算的值存下来，计算过一次之后后面再用到就可以避免重复计算了。

int best = Integer.MAX_VALUE;
List<List<Integer>> tri = new ArrayList<>();
int[][] hash;//存储已经计算过的节点值
public int memorySearch(int x,int y){
  if(x == tri.size()-1){
    hash[x][y]=tri.get(x).get(y);
    return hash[x][y];
  }
  if(hash[x][y]!= Integer.MAX_VALUE){
    return hash[x][y];
  }
  hash[x][y] = tri.get(x).get(y)+Math.min(
    memorySearch(x+1,y),
    memorySearch(x+1,y+1)
  );
  return hash[x][y];
}

public int minimumTotal(List<List<Integer>> triangles) {
  hash = new int[triangles.size()][triangles.get(triangles.size()-1).size()];
  for(int i = 0; i < hash.length;i++){
    for(int j = 0; j < triangles.get(i).size();j++){
      hash[i][j] = Integer.MAX_VALUE;
    }
  }
  return memorySearch(0,0);
  //return best;

}

时间复杂度$O(n^2)$

方法4：多重循环

实现方式1：自底向上

从终点（最下面一层）出发，逐层向上至终点。

状态：f[i,j]表示从最下面一层到点[i,j]最短路径长度

方程：f[i,j] = a[i,j]+min(f[i+1,j],f[i+1,j+1])

初始化：f[i,j] = a[i,j],其中i是最下面一行

答案：f[0,0]

public int dpUp(List<List<Integer>> triangles){
  hash = new int[triangles.size()][triangles.get(triangles.size()-1).size()];
  for(int i = 0 ;i < triangles.size();i++){
    hash[triangles.size()-1][i] = triangles.get(triangles.size()-1).get(i);
  }
  for(int i =triangles.size()-2; i >= 0 ;i--){
    for(int j = 0 ;j <i+1;j++){
      hash[i][j] = triangles.get(i).get(j) + Math.min(hash[i+1][j],hash[i+1][j+1]);
    }
  }
  return hash[0][0];
}

实现方式2：自顶向下

从起点（顶点）出发，逐层向下至最后一层。

状态：f[i,j]表示从最顶点到点[i,j]最短路径长度

方程：f[i,j] = a[i,j]+min(f[i-1,j-1],f[i-1,j])

初始化：f[0,0] = a[0,0]

答案：min(f[i,j]),其中i是最下面一层

public int dpDown(List<List<Integer>> triangles){
  hash = new int[triangles.size()][triangles.get(triangles.size()-1).size()];
  hash[0][0] = triangles.get(0).get(0);
  for(int i =1; i < triangles.size();i++){
    for(int j = 0 ;j <i+1;j++){
      if(j==0){
        hash[i][j] = triangles.get(i).get(j) + hash[i-1][j];
      }
      else if(j == i){
        hash[i][j] = triangles.get(i).get(j) + hash[i-1][j-1];
      }
      else{
        hash[i][j] = triangles.get(i).get(j)+Math.min(hash[i-1][j-1],hash[i-1][j]);
      }
    }
  }
  int min = Integer.MAX_VALUE;
  for(int i = 0;i < triangles.get(triangles.size()-1).size();i++){
    if(hash[triangles.size()-1][i] < min){
      min = hash[triangles.size()-1][i];
    }
  }
  return min;
}

总结一下

什么时候用DP

三个条件满足其一则极有可能是需要用DP求解：

1. 求最大、最小值
2. 判断是否可行
3. 统计方案个数

什么时候不用DP

三个条件满足其一则极不可能用DP：

1. 输出所有方案
2. 给得是集合，不是序列（元素顺序不可换）
3. 暴力算法的时间复杂度已经是多项式复杂度了（n^2,n^3）,dp擅长将指数复杂度优化到多相似复杂度

动态规划四要素：

状态：f[][]的含义，最难！

方程：状态之间的联系，怎么用小状态算大状态

初始化：最小状态是什么，起点

答案：最大状态是什么，终点

两种方法：

1. 自顶向下：从起点出发到终点
2. 自底向上：从终点出发，反推至起点

VS递归三要素

• 定义（状态）
  • 接受了什么参数
  • 做了什么事情
  • 返回了什么值
• 拆解（方程）
  • 符合将参数变小
• 出口（初始化）
  • 什么时候可以直接return

坐标型动态规划

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

> [[1,3,1],
>  [1,5,1],
>  [4,2,1]]
>
>

>

Given the above grid map, return

> 7
>

>

. Because the path 1→3→1→1→1 minimizes the sum.

分析

坐标性动态规划

状态：f[i,j]表示从(0,0)出发走到(i,j)的路径长度

方程：f[i,j] = a[i,j] + min(f[i-1,j],f[i,j-1]),只能从左边和上边走过来

初始化：初始化二维数组时，初始化第0行和第0列

答案：f[end,end]

代码

class Solution {
        public int minPathSum(int[][] grid) {
        int[][] path = new int[grid.length][grid[0].length];
        path[0][0] = grid[0][0];
        for(int i = 1; i < grid[0].length;i++){
            path[0][i] = grid[0][i] + path[0][i-1];
        }
        for(int j = 1; j < grid.length;j++){
            path[j][0] = grid[j][0] + path[j-1][0];
        }
        
        for(int i = 1; i < grid.length;i++) {
            for (int j = 1; j < grid[0].length; j++) {
                path[i][j] = grid[i][j] + Math.min(path[i - 1][j], path[i][j - 1]);
            }
        }
        return path[grid.length-1][grid[0].length-1];
    }
}

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

求从左上角走到右下角的方案个数，到右下角可能从上面或者左边的点过来。

状态：f[i,j]：从(0,0)到(i,j)的方案个数

方程：f[i,j] = f[i-1,j]+f[i,j-1]，走到[i,j]有两种方式，从[i-1,j]和从[i,j-1]，两种方式方案数加和为走到[i,j]点的总方案数

初始化：第0行和第0列的方案数为1，f[i,0]=f[0,j]=1

结果：f[m,n]，右下角元素的状态值

public class UniquePath {
    public int uniquePaths(int m, int n) {
        int[][] nums= new int[m][n];
        //初始化
        for(int i = 0; i < m;i++){
            nums[i][0] = 1;
        }
        for(int i = 0;i < n;i++){
            nums[0][i] = 1;
        }
        //计算f[i][j]
        for(int i = 1;i < m;i++){
            for(int j = 1; j < n;j++){
                nums[i][j] = nums[i-1][j] + nums[i][j-1];
            }
        }
        return nums[m-1][n-1];
    }
    public static void main(String[] args){
        UniquePath test = new UniquePath();
        int m = 1;int n = 2;
        int res = test.uniquePaths(m,n);
        System.out.println(res);
    }
}

Unique Paths II

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

> [
>   [0,0,0],
>   [0,1,0],
>   [0,0,0]
> ]
>
>

>

The total number of unique paths is 2.

在上一题的基础上设置了一些障碍点，所以只需要对障碍点进行判断即可。遇到障碍点时方案数设置为1.

public class UniquePath2 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] nums= new int[m][n];
        //初始化
        if(obstacleGrid[0][0]==1){
            return 0;
        }
        else{
            nums[0][0] = 1;
            for(int i = 1; i < m;i++){
                if(obstacleGrid[i][0]!=1){
                    nums[i][0] = nums[i-1][0];
                }
                else{
                    nums[i][0] = 0;
                }
            }
            for(int i = 1;i < n;i++){
                if (obstacleGrid[0][i]!=1){
                    nums[0][i] = nums[0][i-1];
                }
                else{
                    nums[0][i] = 0;
                }
            }
            //计算f[i][j]
            for(int i = 1;i < m;i++){
                for(int j = 1; j < n;j++){
                    if(obstacleGrid[i][j] == 1){
                        nums[i][j] = 0;
                    }
                    else{
                        nums[i][j] = nums[i-1][j] + nums[i][j-1];
                    }
                }
            }
            return nums[m-1][n-1];
        }
    }
}

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

> Input: 2
> Output:  2
> Explanation:  There are two ways to climb to the top.
>
> 1. 1 step + 1 step
> 2. 2 steps
>
>

>

Example 2:

> Input: 3
> Output:  3
> Explanation:  There are three ways to climb to the top.
>
> 1. 1 step + 1 step + 1 step
> 2. 1 step + 2 steps
> 3. 2 steps + 1 step
>

分析

看成是一维数组，从起点走到终点，每次只能走1或2步。

状态：f[i]走到i点的方案数

转移方程：f[i] = f[i-1]+f[i-1]，因为只能走一步或者两步，所以只能从前一个或者两个格子过来。

初始化：f[0] = 1;f[1] = 1;f[2] = 2

结果：f[n]

public int climbStairs(int n) {
  if(n==1)
    return 1;
  if(n==2)
    return 2;
  int[] res = new int[n];
  //初始化
  res[0] = 1;
  res[1] = 2;
  for(int i = 2;i < n;i++){
    res[i] = res[i-1] +  res[i-2];
  }
  return res[n-1];
}

Jump Game

动态规划可以做，但是贪心法是最优方法

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

分析

数组中的数字表示当前点能够跳跃的最大步长，判断是否可以跳到最后一步：是否有可行方案问题

坐标型动态规划，一维坐标

状态：s[i]，是否能从起点跳到i点

取决于前面是否存在点j：

1. 从起点是否能跳到j点：s[j]
2. 从j是否能跳到i：j+s[j]>=i

转移方程：s[i] = s[j] && j+s[j]>=i（j<i）

初始化：s[0]=1

答案：s[m]，最后一个元素的状态

public boolean canJump(int[] nums) {
  boolean[] canJump = new boolean[nums.length];
  canJump[0] = true;
  for(int i = 1;i < nums.length;i++){
    for(int j = 0;j < i;j++){
      if(canJump[j] && j+nums[j]>=i){
        canJump[i] = true;
        break;
      }
    }
  }
  return canJump[nums.length-1];
}

时间复杂度：$O(n^2)$，提交后超时。

贪心法：

两个指针，一个从头向尾移动，另一个计算能够到达的最远距离。

需要注意的是：左侧指针向右移动时不能超过记录最远到达距离的指针。

public boolean canJump(int[] nums) {
  if(nums.length == 0)
    return false;
  int i = 0;
  int farthest = nums[0];
  while(farthest<nums.length-1 && i < nums.length-1 && i <= farthest){
    farthest = Math.max(farthest,i + nums[i]);
    i++;
  }
  return farthest >= nums.length-1;
}

Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

数组中的数字表示当前点能够跳跃的最大步长，求从起点到终点跳跃最少的方案跳跃次数

求最小，坐标型动态规划

状态：s[i]从起点出发跳到i点需要步数

转移方程：s[i] = min(s[j]+1),j满足条件可以一步跳到i，加个判断

初始化：s[0] = 0

答案：s[m]，最后一个元素状态

public int jump(int[] nums) {
  int[] minStep = new int[nums.length];
  minStep[0] = 0;
  for(int i =1; i < nums.length;i++){
    minStep[i] = Integer.MAX_VALUE;
  }
  for(int i = 1;i < nums.length;i++){
    for(int j = 0;j < i;j++){
      if(j + nums[j] >= i){
        minStep[i] = Math.min(minStep[i],minStep[j]+1);
      }
    }
  }
  return minStep[nums.length-1];
}

时间复杂度：$O(n^2)$，提交后超时。

贪心法：

两个指针，一个从头向尾移动，另一个计算能够到达的最远距离。

需要注意的是：左侧指针向右移动时不能超过记录最远到达距离的指针。

public boolean canJump(int[] nums) {
  if(nums.length == 0)
    return false;
  int i = 0;
  int farthest = nums[0];
  while(farthest<nums.length-1 && i < nums.length-1 && i <= farthest){
    farthest = Math.max(farthest,i + nums[i]);
    i++;
  }
  return farthest >= nums.length-1;
}

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

subqequence：子序列，可以跳着取

substring：子串，相连的，不可以跳着取

思路

DP和二分法

判断是否使用DP：

1. 求最长
2. 一维序列，元素位置不可交换
3. 暴力复杂度是O(2^n)

看成是小人跳木桩，数组的值为木桩的高度，小人每次踩一个更高的木桩

DP

状态：f[i]表示从任意一个木桩出发，从低到高，跳到i点，最多踩过多少个木桩

转移方程：f[i] = max(f[j]+1) j满足：j<i && nums[j]<nums[i]

初始化：f[0] = f[1] = …= f[n-1] = 1 从前面的任何一个点出发跳到此处要经过多少根木桩，初始化时，只经过自己跳到自己踩过的木桩树为1。

结果：max(f[1],f[2],….,f[n-1]) 因为递增子序列不一定以最后一个元素为结尾，这道题要求的是最长的子序列，所以需要在所有的点里面找到最大的值返回。

public int lengthOfLIS(int[] nums) {
  if(nums.length == 0){
    return 0;
  }
  int[] length = new int[nums.length];
  for(int i = 0 ; i < nums.length;i++){
    length[i] = 1;
  }
  for(int i = 1;i < nums.length;i++){
    for(int j = 0;j < i;j++){
      if(nums[i]>nums[j]){
        length[i] = Math.max(length[j]+1,length[i]);
      }
    }
  }
  int max = length[0];
  for(int i = 1 ; i < length.length;i++){
    max = Math.max(max,length[i]);
  }
  return max;
}

时间复杂度$O(n^2)$

二分法

tail[i] -> 用于记录长度为i+1个的LIS的子序列中末尾的【最小】值
size -> 用于记录最大长度。

对于相同长度的LIS子序列，记录末尾值的最小值是因为以该最小值为末尾的子序列更有可能在后续过程中增加长度。

以nums = [4,5,6,3]为例：
len = 1   :      [4], [5], [6], [3]   => tails[0] = 3
								//长度为1的子序列中末尾值最小的是3
len = 2   :      [4, 5], [5, 6]       => tails[1] = 5
								//长度为2的子序列中末尾值最小的是5
len = 3   :      [4, 5, 6]            => tails[2] = 6
								//长度为3的子序列中末尾值最小的是6

此时如果后面又来了一个x
(1) 如果x大于所有tails，那么此时会有长度更长的子序列，以x结尾。那就把这个x放在这个里面，并把长度+1
(2) 如果tails[i-1] < x <= tails[i], 此时不会有长度更长的子序列，但是对于长度为i的子序列，选择x和tails[i]作为结尾相比而言，选择x作为结尾在后续过程中增加长度的可能性更大，所以我们用x更新 tails[i]
size -> 当前最长序列长度
序[0,1,2,3,4,5,6,7,8]
以[2,1,5,3,6,4,8,9,7]为例：
i = 0 --> x = 2, tail = [2,0,0,0,0,0,0,0,0]  -> size = 1
[2]   --> 子序列 2
  
i = 1 --> x = 1, tail = [1,0,0,0,0,0,0,0,0]  -> size = 1
[2,1] --> 子序列[1]
i = 2   --> x = 5, tail = [1,5,0,0,0,0,0,0,0]  -> size = 2
[2,1,5] --> 子序列[1,5]
i = 3    --> x = 3, tail = [1,3,0,0,0,0,0,0,0]  -> size = 2
[2,1,5,3] --> 子序列[1,3]
i = 4       --> x = 6, tail = [1,3,6,0,0,0,0,0,0]  -> size = 3
[2,1,5,3,6] --> 子序列[1,3,6]
i = 5         --> x = 4, tail = [1,3,4,0,0,0,0,0,0]  -> size = 3
[2,1,5,3,6,4] --> 子序列[1,3,4]
i = 6           --> x = 8, tail = [1,3,4,8,0,0,0,0,0]  -> size = 4
[2,1,5,3,6,4,8] --> 子序列[1,3,4,8]
i = 7             --> x = 9, tail = [1,3,4,8,9,0,0,0,0]  -> size = 4
[2,1,5,3,6,4,8,9] --> 子序列[1,3,4,8,9]
i = 8               --> x = 7, tail = [1,3,4,7,9,0,0,0,0]  -> size = 4
[2,1,5,3,6,4,8,9,7] --> 子序列[1,3,4,7,9]

public int lengthOfLIS(int[] nums) {
	int[] tail = new int[nums.length];
    int size = 0;
    //初始化
    for(int i = 0 ; i < nums.length;i++){
        int start = 0 , end = size;
        while(start < end){
            int mid = (start+end)/2 ;
            if(tail[mid]<nums[i]){
                start = mid+1;
            }
            else {
                end = mid;
            }
        }
        tail[start] = nums[i];
        if (start == size) {
            size++;
        }
    }
    return size;
}

序列型动态规划

状态：f[i]表示前i个位置/数字/字符，第i个…

方程：f[i] = g(f[j]),j是i前面的位置

初始化：f[0]

结果：f[n]

Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

给一串字母和单词表，判断是否可以被切分。

状态：f[i]表示前i个字母是否可以被切分。

转移方程：

初始化：

在单词的开始加“^”标记

idx: 0 1 2 3 4 5 6 7 8
ch:  ^ l i n t c o d e
f:   T f f f T f f f T

初始化：
idx: 0 1 2 3 4 5 6 7 8
ch:  ^ l i n t c o d e
f:   T f f f 

计算f[4]时将f[0~4]的字符串^ l i n t切割成如下几种方案：
^ l i n|t  ->  lin和t不在单词表
^ l i|n t  ->  li和nt不在单词表
^ l|i n t  ->  l和int不在单词表
^|l i nt   ->  ^和lint不在单词表->f[4] = T


int[] f;
for(int i = 0 ;i < n;i++){
	for(int j = i-1;j>=0;j--){
      if(f[j] && substring[j,i] in dict){
          f[i] = true;
          break;
      }
	}
}

时间复杂度：O(n^2^L),n为字符串长度，L为词典里的单词个数。

优化：
单词的长度一般不会特别长，设单词表里单词的最大长度为MAXL所以从后往前切割，切割MAXL次即可，如果此时没有答案的话，再继续往前切割也没有必要了。
优化后的时间复杂度为： O(n^L^2)

Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

将字符串切分使得每一段都是回文串，求最少要切几刀。

状态：f[i]，从0到
方程：
初始化：
结果

例子："aabaa"

关于初始化：
在极端情况下，长度为n的字符串切n-1刀，每一段都可以是回文串，长度为1的字符串切0刀，长度为0的字符串切-1刀
所以f[0] = -1

关于f[i]的计算：
对于从0到i的子串的划分，可以划分成如下形式：
1,2,3,...,i-1|i
1,2,3,...j,j+1,...,i


用一个二维数组f[i][j]存储字符串中从i到j是否是一个回文串

双序列型动态规划

给两个序列

状态：f[i,j]表示第一个字符串的前i个，第二个字符串的前j个

转移方程：

初始化：f[i,0],f[0,j]

结果：f[n,m]

例题1：最长公共子串

给出两个字符串，找到最长公共子串，并返回其长度。

样例

给出A=“ABCD”，B=“CBCE”，返回 2

分析：

代码：

public int longestCommonSubstring(String A, String B) {
        // write your code here
        int lenA = A.length();
        int lenB = B.length();
        if(A.length() == 0 || B.length() == 0){
            return 0;
        }
        int max = 0;
        int[][] dp = new int[lenA][lenB];
        //初始化
        for(int i = 0;i < lenA;i++){
            if(A.charAt(i) == B.charAt(0)){
                dp[i][0] = 1;
                max = 1;
            }
        }
        for(int i = 0;i < lenB;i++){
            if(A.charAt(0) == B.charAt(i)){
                dp[0][i] = 1;
                max = 1;
            }
        }
        
        for(int i = 1;i < lenA;i++){
            for(int j = 1;j < lenB;j++){
                if(A.charAt(i) == B.charAt(j)){
                    dp[i][j] = dp[i-1][j-1]+1;
                    max = Math.max(max,dp[i][j]);
                }
            }
        }
        return max;
    }

例题2：最长公共子序列

a b c d 
a c d e

f[abcd][acde] = max(f[abc][acde],f[abcd][acd])

如果最后一个字母不相等，
a[i-1]!=b[i-1]:
f[i][j] = max(f[i-1][j],f[i][j-1])

如果最后一个字母相等，则这个字母已经是公共子序列了，只需在前面的子序列基础之上+1即可
a[i-1] == b[i-1]:
f[i][j] = f[i-1][j-1]+1

Edit Distance

题目

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

给定两个字符串，最少经过多少次修改可以使第一个字符串和诶二哥字符串一样。

分析

s1 = mart
s2 = karma

f[i][j]表示使得s1的前i个字符与s2的前j个字符相等的最少改动次数 
共有三种操作方式

用上面的例子说明：

f[4][5]，为了使得s1的前4个字符与s2的前5个字符相等有三种操作方式：
1. f[3][4] + 1 replace，替换s1的最后一个字符串，需要s1的前3个字符串和s2的前4个字符串相等的修改次数，加上replace的一次操作。
2. f[4][4] + 1 insert，在s1后面插入一个字符'a'，此时s1和s2的最后一个字符相等乐，需要将使得s1的前四个字符和s2的前4个字符相等的操作数，加上insert的一次操作
3. f[3][5]+1 delete，将s1的最后一个字符串删除，需要s1的前三个字符串和s2的前5个字符串相等的操作数加上删除的一次操作

然后需要对上面三种情况取最小值。


综上，
状态：f[i][j]表示使得s1的前i个字符与s2的前j个字符相等的最少改动次数 
转移方程为：
f[i][j] = max(f[i-1][j-1]+1,f[i][j-1]+1,f[-1][j]+1)
初始化：f[i][0] = i,f[0][j] = j
答案：f[n][m]

代码

int minDistance(String word1, String word2) {
  int[][] dis = new int[word1.length()+1][word2.length()+1];
  for(int i = 0; i <= word1.length();i++){
    dis[i][0] = i;
  }
  for(int i = 0; i <= word2.length();i++){
    dis[0][i] = i;
  }
  for(int i= 1;i <= word1.length();i++){
    for(int j = 1; j <= word2.length();j++){
      if(word1.charAt(i-1) == word2.charAt(j-1)){
        dis[i][j] = dis[i-1][j-1];
      }
      else{
        dis[i][j] = Math.min(
          dis[i-1][j-1]+1,//替换
          Math.min(dis[i][j-1]+1,//插入,
                   dis[i-1][j]+1)//删除
        );
      }
    }
  }
  return dis[word1.length()][word2.length()];
}

Distinct Subsequences

题目

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

从S中挑出T有多少种方法

分析

状态：f[i][j] -> 从S的前i个字母中挑出T的前j个字母的方案数

比如F[4][3]:
从S的前4个子母中选出T的前3个字母有多少种方案：
rabb
rab
此时最后一个字母相等，有两种选择方案：
1. 选择最后一个字母，则还需在S的前3个中选择T的前2个，此时方案数=F[3][2]
2. 不选择最后一个字母，则需要在S的前3个中选择3个，此时方案数=F[3][3]
所以这种情况最终的方案数F[4][3] = F[3][2]+F[3][3]

比如F[5][5]:
rabbb
rabbi
此时最后一个字母不相等，那么此时无法选择最后一个字母，则方案数就等于从S的前4个子母中挑出T的前5个，即方案数F[5][5]=F[4][5]

由此转移方程为：
如果最后一个不相等，那就在S的前i-1个字母中挑出T的前j个
f[i][j] = f[i-1][j]
如果最后一个相等，可以在
f[i][j] = f[i-1][j-1]+f[i-1][j]

初始化：f[0][i] = 0,f[i][0] = 0
结果：f[m][n]

代码

public int numDistinct(String s, String t) {
  int[][] nums = new int[s.length()+1][t.length()+1];
  //初始化
  nums[0][0] = 1;
  for(int i = 1; i <= s.length();i++){
    nums[i][0] = 1;
  }
  for(int i = 1; i <= t.length();i++){
    nums[0][i] = 0;
  }
  for(int i = 1;i <= s.length();i++){
    for (int j = 1;j <= t.length();j++){
      if(s.charAt(i-1)==t.charAt(j-1)){
        nums[i][j] = nums[i-1][j-1]+nums[i-1][j];
      }
      else{
        nums[i][j] = nums[i-1][j];
      }
    }
  }
  return nums[s.length()][t.length()];
}

Interleaving String

题目

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

三个字符串s1,s2,s3，判断s3是否可以由s1,s2交替组成（顺序不变，交替着选）

分析

状态：
f[i][j][k]:s1的前i个和s2的前j个是否能够交替组成s3的前k个
k = i + j
状态可以简化为：
f[i][j]:s1的前i个和s2的前j个是否能够交替组成s3的前i+j个

转移方程推导：
f[i][j]=true有如下两种情况：
1. 最后一个字母来自s1,s1的前i-1个字母和s2的前j个字母能够交替组成s3的前i+j-1个，即:s1[i]==s3[i+j] && f[i-1][j]==true
2. 最后一个字母来自s2,s2的前j-1个字母和s1的前i个字母能够交替组成s3的前i+j-1个，即:s2[i]==s3[i+j] && f[i][j-1]==true

综上，转移方程为：
f[i][j] = (f[i-1][j] && s1[i-1] == s3[i+j-1])||
			(f[i][j-1] && s2[j-1]==s3[i+j-1])

初始化：f[i][0] = (s1[0...i-1] == s3[0...i-1])前半段都用s1
		f[0][j] = (s2[0...j-1] == s3[0...j-1])前半段都用s2

结果：f[n][m]

代码

public boolean isInterleave(String s1, String s2, String s3) {
  if(s1.length()+s2.length() != s3.length())
    return false;
  boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
  //初始化
  dp[0][0] = true;
  boolean flag = true;
  for(int i =1 ; i <= s1.length();i++){
    if(flag){
      if(s1.charAt(i-1)==s3.charAt(i-1)){
        dp[i][0] = true;
      }
      else{
        dp[i][0] = false;
        flag = false;
      }
    }
    else{
      dp[i][0] = false;
    }
  }
  boolean flag2 = true;
  for(int i =1 ; i <= s2.length();i++){
    if(flag2){
      if(s2.charAt(i-1)==s3.charAt(i-1)){
        dp[0][i] = true;
      }
      else{
        dp[0][i] = false;
        flag2 = false;
      }
    }
    else{
      dp[0][i] = false;
    }
  }
  for(int i = 1; i <= s1.length();i++){
    for(int j = 1; j <= s2.length();j++){
      dp[i][j] = (dp[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1) ||
                  (dp[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1)));
    }
  }
  return dp[s1.length()][s2.length()];
}