算法思想：动态规划 (Dynamic Programming)

动态规划是算法的重点和难点。一方面我们在实际生活中的许多场景（比如满减凑单，最短路径等等）下都是需要使用到动态规划思想的，这使得其场景总是很复杂；另一方面动态规划的思维逻辑并不直接反应人的思维方式，不像贪心之类的，本身就是人实际的思考方式，这就使得动态规划难以理解。

背包问题（Knapsack problem）

我们以经典的背包问题来引入动态规划概念。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

0-1 背包问题

背包问题有很多变体，这里首先讲最经典的背包问题。0-1背包问题中物品是不可分割的，要么装要么不装，所以叫 0-1 背包问题。0-1 背包是非常经典的算法问题，很多场景都可以抽象成这个问题模型。

问题描述如下：

有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

我们最先想到的是使用贪心算法，但是这个场景不适合贪心算法，物品是不可分割的，当我们将单位重量价值最大的物品放入背包的时候，第二价值大的东西可能已经放不下了，而第二价值大的物品总价值可能比其他物品的总和还要多。

那么我们可以用回溯，将物品放入背包的所有情况全部枚举，然后选择价值最大的那个组合，如下每次选择当前容量最大的那个组合：

/**  
 * 回溯法处理  
 */  
public static List<Integer> resolve(int[] weight, int[] value, int capacity ){  
    return resolve(weight,value,capacity,0,0);  
}  
  
  
private static List<Integer> resolve(int[] weight,int[] value,int capacity,int start,int pValue){  
    if(capacity <= 0 || start >= weight.length){  
        // 没有容量了或者已经是最后一件物品了  
        return Collections.emptyList();  
    }  
  
    List<Integer> select = new ArrayList<>();  
    int maxValue = Integer.MIN_VALUE;  
  
    // 重量没超出限制  
    for(int i = start; i < weight.length; i++){  
        if(weight[i] <= capacity){  
            // 放入下一个  
            List<Integer> list =  resolve(weight,value,capacity-weight[i],i+1,pValue+value[i]);  
            // 计算总价值  
            int v = list.stream().mapToInt(data -> value[data]).sum();  
            v += value[i];  
  
            if(v > maxValue){  
                // 始终放入价值最大的  
                maxValue = v;  
                // 清除旧的  
                select.clear();  
                // 放入  
                select.add(i);  
                select.addAll(list);  
            }  
        }  
    }  
    return select;  
}

由于我们需要尝试每种组合，其效率并不高。假设背包容量很大而物品的重量不高，那么在递归过程中还有栈溢出风险。

我们可以换一种思路来思考这个问题。

我们认为每次选择放入或者不放入的时候的结果都会引起状态的变化，这里影响的是当前容量，当前价值，而每次选择的状态的基底都是上次选择的结果，依此类推，在对每个物品完成选择之后，最终的价值最高的选择就是我们需要找的答案。

/**  
 * 动态规划处理  
 * @param weight  
 * @param value  
 * @param capacity  
 * @return  
 */  
public static List<Integer> resolveDP(int[] weight, int[] value, int capacity){  
    // 状态转移，每次转移的状态有容量变化 与 物品选择与否 和 物品总价值  
    Map<Integer, Map<Integer,Integer>> map = new HashMap<>();  
  
    // 初始化  
    for(int i = 0; i < weight.length; i++){  
        // 不放入的情况下价值为0  
        Map<Integer, Integer> v = new HashMap<>();  
        v.put(0, 0);  
        map.put(i, v);  
    }  
  
    // 第一件物品放入的的情况下，其价值  
    if(weight[0] <= capacity){  
        map.get(0).put(weight[0], value[0]);  
    }  
  
    for(int i = 1; i < weight.length; i++){  
        // 当前物品只有放入和不放入两种选择，而其状态只能由上个状态过来  
  
        // 当前状态  
        Map<Integer, Integer> v = map.get(i);  
        Map<Integer, Integer> prev = map.get(i - 1);  
        for(Map.Entry<Integer, Integer> entry : prev.entrySet()){  
            // 上个加上这个是否已经超出了限制，如果没有则放入  
            Integer oldKey = entry.getKey();  
            Integer key = oldKey + weight[i];  
            if(key <= capacity){  
                // 此时可能存在两种情况  
                // 一是前面的的状态可能有相同的重量的价值  
                Integer old = prev.getOrDefault(key,0);  
  
                // 二是当前重量的重价值  
                int newValue = entry.getValue() + value[i];  
  
                // 放入较大的一个  
                v.put(key, Math.max(old,newValue));  
            }else {  
                // 不能放入，就是上个重量的价值  
                v.put(oldKey, entry.getValue());  
            }  
        }  
    }  
  
    // 由于状态是一步步转移下来的最后的重量里面选择价值最高的就是结果  
    Map<Integer, Integer> v = map.get(weight.length - 1);  
    // 取价值最大的  
    int maxValue = Integer.MIN_VALUE;  
    Map.Entry<Integer, Integer> select =null;  
    for (Map.Entry<Integer, Integer> entry : v.entrySet()) {  
        if (entry.getValue() > maxValue) {  
            maxValue = entry.getValue();  
            select = entry;  
        }  
    }  
  
    // 逆向恢复选择的物品  
    List<Integer> selectList = new ArrayList<>();  
  
    if (select != null){  
        int nowWeight = select.getKey();  
        int nowValue = select.getValue();  
        for (int i = weight.length - 1 ; i >= 0; i--) {  
            // 上个状态  
            Integer val = map.getOrDefault(i-1,Collections.emptyMap()).get(nowWeight);  
            // 三种情况，不存在或者小于价值小i与当前价值的时候，之前的物品肯定被选择了  
            if (val==null || val < nowValue){  
                // 物品被选择了  
                selectList.add(i);  
                // 去掉物品的重量与价值  
                nowWeight -= weight[i];  
                nowValue -= value[i];  
            }  
        }  
    }  
  
    return selectList;  
}

首先我们构建了一个map，存储当前物品所有的可能的总重量的价值。

比如，对于第一次选择后，第一件物品i=0,它只有两种状态，即不放入的时候总重量是0，其对应的价值也是0，如果重量小于目标重量，那么有一个放入后的总重量w[0]其对应的价值是v[0]。

那么我们下一次选择后也就是第二件物品i=1,它只能由第一次选择后的状态转移过来，那么第二次选择后的状态就总数m = 第一次选择的总数n × 第二次的选择数量x。如果第二次的重量超出容量了，那么就只能选择不放入，就只有一种选择，那么第二次选择后的状态就和第一次选择后的状态是一样的。如果放入后重量没有超出容量，有放入和不放入两种选择，状态如下：

依此类推我们可以一步步将状态转移到全部物品选择完成后的情况。从最后的状态中取出价值最高的状态便是我们需要的结果。

我们可以通过该状态从后向前推演出选择了哪些物品：

// 逆向恢复选择的物品  
List<Integer> selectList = new ArrayList<>();  

if (select != null){  
    int nowWeight = select.getKey();  
    int nowValue = select.getValue();  
    for (int i = weight.length - 1 ; i >= 0; i--) {  
        // 上个状态  
        Integer val = map.getOrDefault(i-1,Collections.emptyMap()).get(nowWeight);  
        // 三种情况，不存在或者小于价值小i与当前价值的时候，那么当前物品肯定被选择了  
        if (val==null || val < nowValue){  
            // 物品被选择了  
            selectList.add(i);  
            // 去掉物品的重量与价值  
            nowWeight -= weight[i];  
            nowValue -= value[i];  
        }  
    }  
}  

思想

从上面的例子可以看出，动态规划的核心是状态转移的推断过程。

应用场景与特征

动态规划适用于解决多阶段决策最优解问题，解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

特征

1. 最优子结构

动态规划的解题过程是从一个状态向下一个状态转移的过程。最优子结构指的是，问题的最优解包含子问题的最优解，也就是说我们可以从每个阶段的最优解推出逐步推导出问题的最优解。以上面的背包问题为例，对于容量为C的背包和物品列表items[0..n-1]，最大价值map.get(n).get(C)取决于：

• 不选第n-1个物品时的最大价值 map.get(n-1).get(C) (子问题1)
• 选第n-1个物品时的最大价值 value[n-1] + map.get(n-1).get(C - weight[n-1]) (子问题2)
• 取这两者的最大值。map.get(n).get(C)的最优解由其子问题map.get(n-1).get(C)和map.get(n-1).get(C - weight[n-1])的最优解组合而来

2. 无后效性

无后效性的含义是当前阶段只与上个阶段后的状态有关，当前阶段处理后的状态一旦确定，下个阶段无论如何变化都不会影响当前阶段的状态，无后效性也是马尔科夫链的基本要求，当前状态只与上个状态有关。以上面的背包问题为例，map.get(i).get(c)（考虑前i个物品，背包容量为c时的最大价值）这个状态的值只取决于i和c。一旦这个值被计算出来，后续计算map.get(i+1).get(c)时，只会用到map.get(i).get(c)的值（以及物品i+1的信息），而不会去改变map.get(i).get(c)的值，也不会关心map.get(i).get(c)是通过考虑哪些物品的哪种组合得到的。

3. 重复子问题

不同的决策序列在到达某个相同的阶段的时候可能产生重复的状态，这也意味着获得最优解组合可能不止有一个。以上面背包问题为例，第2和第3件物品都是相同重量相同价值，那么单独选择第二件和选择第三件的都是一样的，即在第三件（i=2）之后，map.get(2).get(C)的组合可能选择了第二件也可能是只选择了第三件。

总结

• 最优子结构： “大问题的最优解由小问题的最优解组成” -> 让我们能分解问题。
• 无后效性： “未来只与现在有关，与过去无关” -> 让我们能定义清晰的状态和状态转移。
• 重复子问题： “同样的计算做了很多遍” -> 让我们通过存储计算结果避免重复工作，提升效率。

解法思路

以一个零钱兑换问题为例。问题描述如下：

给你一个整数数组 `coins` ，表示不同面额的硬币；以及一个整数 `amount` ，表示总金额。

计算并返回可以凑成总金额所需的 **最少的硬币个数** 。如果没有任何一种硬币组合能组成总金额，返回 `-1` 。

你可以认为每种硬币的数量是无限的。

**示例 1：**

**输入：**coins = `[1, 2, 5]`, amount = `11`
**输出：**`3` 
**解释：**11 = 5 + 5 + 1

**示例 2：**

**输入：**coins = `[2]`, amount = `3`
**输出：**-1

**示例 3：**

**输入：**coins = [1], amount = 0
**输出：**0

**提示：**

- `1 <= coins.length <= 12`
- `1 <= coins[i] <= 231 - 1`
- `0 <= amount <= 104`

我们首先使用回溯法暴力的处理该问题：

/**  
 * 回溯法处理  
 * @param coins  
 * @param amount  
 * @return  
 */  
public static Map<Integer,Integer> coinChange(int[] coins, int amount) {  
    if (amount <= 0) return Collections.emptyMap();  
  
    int max = -1;  
    Map<Integer,Integer> map = new HashMap<>();  
  
    for (int coin : coins) {  
        if (amount >= coin) {  
            //尝试放入一枚后对剩余进行处理  
            Map<Integer, Integer> integerIntegerMap = coinChange(coins, amount - coin);  
            // 使用的硬币总数  
            int sum = integerIntegerMap.values().stream().mapToInt(i -> i).sum();  
            // 加上当前使用的一枚  
            sum = sum + 1;  
  
            // 取总数最小的  
            if (max==-1 || sum < max){  
                max = sum;  
                map.clear();  
                map.putAll(integerIntegerMap);  
                Integer coinNum = map.getOrDefault(coin, 0);  
                map.put(coin,coinNum + 1);  
            }  
        }  
    }  
  
  
    int sum = map.entrySet().stream().mapToInt(d -> d.getKey() * d.getValue()).sum();  
  
    if (sum != amount ) return Collections.emptyMap();  
  
    return map;  
}

回溯法的时间复杂度极高，所以在凑高金额时间加上多币值的情况下其执行时间会非常非常长（本质上是一个更加复杂的爬楼梯问题（斐波那契数列））。

1. 状态转移表

以上面的找零案例为例，我们在在回溯法的基础上画出递归树：a = amount 总价值，c = coins 供选择的币值类型。

                                    f(a)
                                   /     \
                            f(a-c[0])....f(a-c[i])
                               /   \      /   \
        f(a-c[0]-c[0])...f(a-c[0]-c[i])...f(a-c[i]-c[0])...f(a-c[0]-c[1])
        ...................
        /             \
    c[0]..............c[0]

比如我们的币值有 coins = [1,5,10,20,50,100] 而我们需要凑 amount = 108 元。那么譬如f(103) 、 f(98) 和 f(88)等等都会被多次执行，存在重复子问题。那么我们的一项优化可以是，将这些结果缓存起来供下次使用，但是这还不够好，我们需要使用动态规划的方法来思考此问题。

我们每次都选择一张其中一种币值，我们每次选择都会改变以下状态：已经凑成的总金额。

在第一次选择一张面额后结果有以下可能：

第二次选择一张面额后有以下可能：

依此类推我们可以在第五次的我们可以凑出108。由于金额是必然递增的，我们可以逆推出每种面额的使用了多少张。

2. 状态转移方程

转移表可以直观的展开表示每次状态转移之后所有的可能。

我们已经确认每个阶段都是用每个面额与上个阶段的凑出的总额相组合，并且保存最少的能凑出该总额的货币数量的最后一个选择的面额用来逆推出该总额各个面额货币使用了多少张。

那么我们假设之前的状态是 be_amount[] 存储之前阶段已经凑成的总额的最后一个选择的面额，现在我们要凑成的状态是 amount[] ，那么他们的递推关系如下（其中j是上个状态总额的位置，i是当前面额的位置）：

                              be_amount[be_amount[j]+coins[i]]  //如果当前总额之前凑过
amount[b_amount[j]+coins[i]] = 
                              i   // 如果总额每凑过，则保存此次凑的的面额

如果之前已经凑过了该金额就以之前的金额为准，否则就是新凑成的金额，当前面额就是最后一个选择。

零钱兑换

• 根据状态转移表，我们可以得出实现如下：

/**  
 * 动态规划  
 * @param coins  
 * @param amount  
 * @return  
 */  
public static Map<Integer,Integer> coinChangeDP(int[] coins, int amount) {  
    // 由于每次金额只会增长，所以得到key之后可以逆向推出每个面额用了多时少  
    // key已凑成的金额 value对应的最后一个硬币位置  
    Map<Integer,Integer> dp = new HashMap<>();  
  
    // 初始化  
    for (int i=0 ;i<coins.length;i++) {  
        if (amount >= coins[i]) {  
            dp.put(coins[i],i);  
        }  
    }  
    // 无法凑成  
    if (dp.isEmpty()) return Collections.emptyMap();  
  
    boolean find = false;  
  
    // 上次状态，用来加速状态迁移过程，下次状态只与上次有关  
    Map<Integer,Integer> before = new HashMap<>(dp);  
  
    // 只有无法凑成或者已经凑成的情况下才会终止  
    // 每次都对上次状态进行考察  
    while (!find) {  
        // 每次凑一张  
        // 上次凑数的结果  
        Set<Integer> amounts = before.keySet();  
        // 本次凑数的结果  
        Map<Integer,Integer> now = new HashMap<>();  
  
        for (int i = 0; i < coins.length; i++) {  
            // 上个状态的币值  
            for (Integer a : amounts) {  
                int newAmount = coins[i] + a;  
                // 符合条件  
                if (newAmount <= amount) {  
                    // 只保留最最小次数的金额  
                    if (!dp.containsKey(newAmount)) {  
                        // 不存在就存入，且需要继续寻找  
                        // 可能存在重复，存在重复就不放入了  
                        now.putIfAbsent(newAmount, i);  
                    }  
                    if (newAmount == amount) {  
                        find = true;  
                        // 已经找到  
                        break;  
                    }  
                }  
            }  
        }  
        // 上次状态更新  
        before = now;  
        //存入本次的结果  
        dp.putAll(now);  
        // 无法凑出的情况  
        if(now.isEmpty()) break;  
    }  
  
    Map<Integer,Integer> result = new HashMap<>();  
  
    if (find){  
        // 逆向推导出哪些面额用了多少  
       int lease = amount;  
  
       while (lease > 0){  
           Integer index = dp.get(lease);  
           Integer old = result.getOrDefault(index, 0);  
           result.put(index,old+1);  
           lease -= coins[index];  
       }  
  
    }  
  
    return result;  
}

这里使用三个map存每个金额最后的选择面额。dp是已经凑过的所有的金额，就是整个状态转移表，before是上个阶段的状态，now是当前的凑额状态。

需要注意的是我们每次凑完之后都会将更新整个状态转移表，并替换上个状态为当前的状态。这使得我们的效率变得更高。同时我们还需要注意如果之前已经有了相同的金额则不处理。

• 根据状态转移方程，我们可以得出实现如下：

/**  
 * 动态规划 -- 状态转移方程  
 * @param coins  
 * @param amount  
 * @return  
 */  
public static Map<Integer,Integer> coinChangeDP2(int[] coins, int amount) {  
    // 由于每次金额只会增长，所以得到key之后可以逆向推出每个面额用了多时少  
    // key已凑成的金额 value对应的最后一个硬币位置  
    Map<Integer,Integer> dp = new HashMap<>();  
  
    // 初始化  
    for (int i=0 ;i<coins.length;i++) {  
        if (amount >= coins[i]) {  
            dp.put(coins[i],i);  
        }  
    }  
    // 无法凑成  
    if (dp.isEmpty()) return Collections.emptyMap();  
  
    // 上次状态，用来加速状态迁移过程，下次状态只与上次有关  
    Map<Integer,Integer> before = new HashMap<>(dp);  
  
    // 下次放入  
    boolean find = coinChangeDP2(coins,amount,dp,before);  
  
    if(!find){  
        return Collections.emptyMap();  
    }  
  
    Map<Integer,Integer> result = new HashMap<>();  
    // 逆向推导出哪些面额用了多少  
    int lease = amount;  
  
    while (lease > 0){  
        Integer index = dp.get(lease);  
        Integer old = result.getOrDefault(index, 0);  
        result.put(index,old+1);  
        lease -= coins[index];  
    }  
  
    return result;  
}  
  
/**  
 * 动态规划 -- 状态转移方程  
 * @param coins  
 * @param amount  
 * @return  
 */  
private static boolean coinChangeDP2(int[] coins, int amount,Map<Integer,Integer> dp, Map<Integer,Integer> before) {  
    // 每次凑一张  
    // 上次凑数的结果  
    Set<Integer> amounts = before.keySet();  
    // 本次凑数的结果  
    Map<Integer,Integer> now = new HashMap<>();  
  
    for (int i = 0; i < coins.length; i++) {  
        // 上个状态的币值  
        for (Integer a : amounts) {  
            int newAmount = coins[i] + a;  
            // 符合条件  
            if (newAmount <= amount) {  
                // 只保留最最小次数的金额  
                if (!dp.containsKey(newAmount)) {  
                    // 不存在就存入，且需要继续寻找  
                    // 可能存在重复，存在重复就不放入了  
                    now.putIfAbsent(newAmount, i);  
                }  
                if (newAmount == amount) {  
                    //存入本次的结果  
                    dp.putAll(now);  
                    return true;                }  
            }  
        }  
    }  
  
    // 无法凑出的情况  
    if(now.isEmpty()) return false;  
    //存入本次的结果  
    dp.putAll(now);  
  
    // 下次放入  
    return coinChangeDP2(coins, amount, dp, now);  
}

我们使用递归的方式表示每次选择过程。和状态转移表一样，使用三个map表示整个状态，之前的状态和当前状态。

此实现更加直观的体现了凑数过程：

• 每次一张，每张与上个状态进行组合
• 组合结果就是当前状态
• 如果凑成了则返回true
• 如果每凑成则返回false
• 否则继续下个阶段的凑数

编辑距离（Edit Distance）算法

编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是 0。

编辑距离算法是用来评估两个字符串相似度的算法，它有两种完全不同的思路，一是评估两个字符串的差异到底有多大，二是评估两个字符串到底有多相似。

这两种思路分别对应着莱文斯坦距离和最长公共子串长度。

莱文斯坦距离（Levenshtein distance）

莱文斯坦距离用来衡量字符串差异到底有多大，其值越高，差异就越大。
莱文斯坦距离允许增加、删除、替换字符这三个编辑操作。

我们依然可以使用回溯的方法来计算距离

public static int levenshtein(String word1, String word2) {  
    char[] source = word1.toCharArray();  
    char[] target = word2.toCharArray();  
  
    // 对于每一个字符都有三种选择，删除、增加和替换  
    int i = 0;  
    int j = 0;  
  
    return levenshtein(source,target,i,j);  
}  
  
/**  
 * 回溯法  
 * @param source  
 * @param target  
 * @param i  
 * @param j  
 * @return  
 */  
private static int levenshtein(char[] source, char[] target , int i,int j) {  
    if(i == source.length || j == target.length){  
         // 一个已经到末尾了，另一个还没有，那么他们的长度距离就是剩下距离  
        if(i<source.length){  
            return source.length - i;  
        }  
        if (j<target.length){  
            return target.length - j;  
        }  
        return Math.abs(source.length-target.length);  
    }  
  
    if (source[i] == target[j]) {  
         return levenshtein(source, target, i + 1, j + 1);  
    }else {  
        // 三种选择  
        // 删除一个字符  
        int del = levenshtein(source,target,i+1,j);  
        // 增加一个字符  
        int add = levenshtein(source,target,i,j+1);  
  
        int min = Math.min(del,add);  
  
        // 修改一个字符  
        int edit = levenshtein(source, target, i + 1, j + 1);  
  
        return Math.min(edit, min) + 1;  
    }  
}

但是我们可以很容易注意到类似i=3,j=4这样的状态实际上会被重复计算了多次，存在大量的重复子问题。

那么我们可以尝试使用动态规划来解决这个问题。
首先，我们需要明确当前对于需要对比的两个字符串source[]和target[] 他们需要对比的位置 i 和 j 的状态只能从以下三个位置转移过来 ：

1. i-1 和 j 对应插入一个字
2. i 和 j-1 对应删除一个字
3. i-1 和 j-1 对应修改（替换一个字）

那么状态转移有以下两种情况

• 如果source[i]==target[j] 则直接等于上个状态替换了一个字的情况，即i-1 j-1的距离
• 如果source[i]！=target[j] 则其距离等于上个状态三种情况最小的一个加一，即min(x,y,z) + 1 其中x是

以source = abcdef target = lma为例，其状态转移表如下：

则实现如下：

/**  
 * 莱文斯坦距离（Levenshtein distance）  
 * @param word1  
 * @param word2  
 * @return  
 */  
public static int levenshtein(String word1, String word2) {  
    char[] source = word1.toCharArray();  
    char[] target = word2.toCharArray();  
    // 每次对比一个字符  
    int[][] dp = new int[source.length][target.length];  
  
    // 初始化第一行 第一行只能从前一个位置转移过来  
    for (int j = 0; j < target.length; j++) {  
        if (source[0] == target[j]) {  
            dp[0][j]= j;  
        }else {  
            // 不相等则增加一个编辑  
            dp[0][j] = j==0 ? 1 : (dp[0][j-1]+1);  
        }  
    }  
  
    // 初始化第一列 第一列只能从前一个位置转移过来  
    for (int i = 0; i < source.length; i++) {  
        if (source[i] == target[0]) {  
            dp[i][0]= i;  
        }else {  
            // 不相等则增加一个编辑  
            dp[i][0] =  i==0 ? 1 : (dp[i-1][0]+1);  
        }  
    }  
  
    // 上个状态只能由 i-1 j, i j-1和i-1 j-1转移过来则取他们  
    for (int i = 1; i < source.length; i++) {  
        for (int j = 1; j < target.length; j++) {  
            if (source[i] == target[j]) {  
                // 直接等于替换一个字的情况  
                dp[i][j] = dp[i-1][j-1];  
            }else {  
                // 对于每一个字符都有三种选择，删除、增加和替换  
                int i1 = dp[i - 1][j];  
                int j1 = dp[i][j-1];  
                int i1j1 = dp[i-1][j-1];  
                // 取最小的  
                int min = Math.min(i1 + 1, j1 + 1);  
                dp[i][j] = Math.min(min,i1j1+1);  
            }  
        }  
    }  
  
    return dp[source.length-1][target.length-1];  
}

dp状态表的含义是，对于source[i] 和 target[j] 表示字符串source[0...i]与target[0....j]的编辑距离。

最长公共子串长度（Longest common substring length）

最长公共子串长度用来衡量字符串到底有多相似，其值越高，差异就越大。
最长公共子串长度只允许增加、删除字符这两个编辑操作。

我们依然是每个阶段取一个字符对比，有两种情况：

• 位置i和j对应的字符相同，则最大公共字串加一，继续对比下一个字符i+1和j+1
• 位置i和j对应的字符不相同。则有两种情况选择，一是删除一个字符，继续对比i+1和j;二是增加一个字符，继续对比i 和 j+1。

同样我们可以分析出有大量的重复子问题。

也同样的，我们可以得到，对于i 和 j 位置的字符，他们的状态只可能来自于一下几种情况：

1. i-1 和 j-1 匹配的情况
2. i 和 j-1 删除一个字符的情况
3. i-1 和 j 增加一个字符的情况

那么对于i 和 j 位置的字符，依然有两种情况需要讨论

• source[i] == target[j] ，则在匹配的情况下加一
• source[i] != target[j] ，则取三种情况最大的一种

            dp[i-1][j-1] + 1 // source[i] == target[j]
dp[i][j] =  
            max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) // source[i] != target[j]

实现如下：

/**  
 * 最长公共子串长度（Longest common substring length）  
 * @param word1  
 * @param word2  
 * @return  
 */  
public static int common(String word1, String word2){  
    char[] source = word1.toCharArray();  
    char[] target = word2.toCharArray();  
    // 每次对比一个字符  
    int[][] dp = new int[source.length][target.length];  
  
    // 初始化第一行 第一行只能从前一个位置转移过来  
    for (int j = 0; j < target.length; j++) {  
        if (source[0] == target[j]) {  
            // 相等则为1  
            dp[0][j] = 1;  
        }else {  
            if(j==0){  
                dp[0][j] = 0;  
            }else {  
                dp[0][j] = dp[0][j-1];  
            }  
        }  
    }  
  
    // 初始化第一列 第一列只能从前一个位置转移过来  
    for (int i = 0; i < source.length; i++) {  
        if (source[i] == target[0]) {  
            // 相等则为1  
            dp[i][0] = 1;  
        }else {  
            if(i==0){  
                dp[i][0] = 0;  
            }else {  
                dp[i][0] = dp[i-1][0];  
            }  
        }  
    }  
  
    // 上个状态只能由 i-1 j, i j-1和i-1 j-1转移过来则取他们  
    for (int i = 1; i < source.length; i++) {  
        for (int j = 1; j < target.length; j++) {  
            if (source[i] == target[j]) {  
                // 直接等于替换一个字的情况  
                int i1j1 = dp[i-1][j-1] + 1;  
                dp[i][j] = i1j1;  
            }else {  
                // 对于每一个字符都有三种选择，删除、增加和替换  
                int i1 = dp[i - 1][j];  
                int j1 = dp[i][j-1];  
                int i1j1 = dp[i-1][j-1];  
                // 取最小的  
                int max = Math.max(i1, j1);  
                dp[i][j] = Math.max(max,i1j1);  
            }  
        }  
    }  
  
    return dp[source.length-1][target.length-1];  
}

dp状态表的含义是，对于source[i] 和 target[j] 表示字符串source[0...i]与target[0....j]的最大公共子串长度。

最长递增子序列

问题描述如下：

给你一个整数数组 `nums` ，找到其中最长严格递增子序列的长度。

**子序列** 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，`[3,6,2,7]` 是数组 `[0,3,1,6,2,2,7]` 的子序列。

 

**示例 1：**

**输入：**nums = [10,9,2,5,3,7,101,18]
**输出：**4
**解释：**最长递增子序列是 [2,3,7,101]，因此长度为 4 。

**示例 2：**

**输入：**nums = [0,1,0,3,2,3]
**输出：**4

**示例 3：**

**输入：**nums = [7,7,7,7,7,7,7]
**输出：**1

**提示：**

- `1 <= nums.length <= 2500`
- `-104 <= nums[i] <= 104`

**进阶：**

- 你能将算法的时间复杂度降低到 `O(n log(n))` 吗?

我们如此处理，我们分配长度为n的数组，分别存储i+1长度的最后一个元素。那么对于某个元素x，有如下处理：

• 从len（len是当前最大长度）开始，对比len中的每一个元素，如果任何一个元素当前元素，则表示当前元素x是len+1中的元素
• 如果不大于len中的任何一个元素，则向前对比len-1中的每个元素
• 如果都不大于，则表示是长度为1的序列里面的元素

public static int lengthOfLIS(int[] nums) {  
    // 每个数字所在的最长序列，key是所属序列的长度，v是该长度下末尾的所有的数字  
    Map<Integer,List<Integer>> dp = new HashMap<>();  
    // 第一个数字的序列长度为1  
    List<Integer> one = dp.getOrDefault(1, new ArrayList<>());  
    one.add(nums[0]);  
    dp.put(1, one);  
  
    int len = 1;  
    // 对每一个数字进行考察  
    for (int i = 1; i < nums.length; i++){  
        // 从最长的序列开始考察  
        for (int j=len; j>0; j--){  
            List<Integer> list = dp.get(j);  
            boolean find = false;  
            // 是否有比当前元素小的元素，如果有那当前元素就是属于下一个长度的元素  
            for (Integer integer : list) {  
                if(integer < nums[i]){  
                    // 插入到下一个  
                    List<Integer> value = dp.getOrDefault(j + 1, new ArrayList<>());  
                    value.add(nums[i]);  
                    dp.put(j+1,value);  
                    find = true;  
                    if(len == j){  
                        len = j+1;  
                    }  
                    break;  
                }  
            }  
            if(find){  
               break;  
            }  
            if(j==1){  
                // 第一个还是没有找到则将元素放入序列长度为1的列表  
                list.add(nums[i]);  
            }  
        }  
    }  
  
    return len;  
}

我这里使用一个map存储每各个长度的末尾数字。

我们的一个优化思路是，既然我们比序列末尾元素合集中的任意一个元素大就行，那么我们并不用存储每个元素，只需要存储最小的那个就行。那么我们可以将map做成一个一维数组，这样还可以使用二分搜索加速位置的过程。优化后代码如下：

/**  
 * 优化版本  
 * @param nums  
 * @return  
 */  
public static int lengthOfLIS(int[] nums) {  
    // 每个长度序列的 最后一个数字，他们合集中最小的一个  
    int[] dp = new int[nums.length];  
    // 第一个数字的序列长度为1  
    dp[0]= nums[0];  
  
    int len = 1;  
    // 对每一个数字进行考察  
    for (int i = 1 ; i < nums.length ; i++) {  
        int num = nums[i];  
        // 二分查找每个位置  
        int index = lastLte(dp, num, len);  
        if(index == -1){  
            // 不存在大于等于当前元素的位置则表示当前元素是最大的  
            dp[len++] = num;  
        }else {  
            // 大于等于该元素替换该位置的元素  
            dp[index] = num;  
        }  
    }  
  
    return len;  
}  
  
// 查找第一个大于等于目标元素的位置  
private static int lastLte(int[] list, int target,int len){  
    int low = 0;  
    int high = len - 1;  
    // 开始查找  
    while(low <= high){  
        int mid = low + ((high - low) >> 1);  
        if(list[mid] >= target){  
            // 当前元素大于等于目标值，向前查找  
            high = mid - 1;  
        }else {  
            // 如果小于则向后查找  
            low = mid + 1;  
        }  
    }  
  
    // 如果没有越界且等于目标值，则返回。  
    if(low < len && list[low] >= target){  
        return low;  
    }  
  
    return -1;  
}

时间复杂度是nlogn。

算法思想比较

贪心 vs 动态规划 ：

• 贪心的局部最优选择需满足贪心选择性质 ，而动态规划通过子问题最优解构造全局最优解
• 动态规划适用于贪心失效的场景（如0-1背包问题）

回溯 vs 分治 ：

• 回溯是“试错”过程，通过剪枝减少搜索空间；分治的子问题相互独立
• 回溯常用于求解可行解，而分治更关注问题分解

动态规划 vs 分治 ：

• 动态规划处理子问题重叠的情况，通过记忆化避免重复计算；分治的子问题通常不重叠