有个疑问：
以下内容涉及“如何编程计算莱文斯坦距离？”一节。

（1）文中对递归树中的状态三元组(i, j, edist)的解释是，“状态包含三个变量 (i, j, edist)，其中，edist表示处理到 a[i] 和 b[j] 时，已经执行的编辑操作的次数。”这里的“处理到a[i]和b[j]时”，其实是在说将要处理但还并未处理a[i]和b[j]。edist并不包括对a[i]和[j]的编辑操作。递归树图片后紧接着的图片中，(i, j, min_edist)的min_edist也并不包括对a[i]和[j]的编辑操作。

（2）而二维状态表图片中每格的值和动态规划的实现代码中minDist[i][j]两者均代表：到处理完a[i]和b[j]之后为止，已经执行的编辑操作的最少次数。根据这个意思，可知状态转移方程中的min_edist(i, j)也是包括对a[i]和[j]的编辑操作的。如果按照（1）中的意思，状态转移方程中的min_edist(i, j)就不应该包括对a[i]和[j]的编辑操作，也不应该判断a[i]和b[j]是否相等，而应该判断的是a[i - 1]和b[j - 1]是否相等；并且动态规划的实现代码中循环终止条件就不应是小于n或m，而应是小于等于n或m。

为什么会有（1）与（2）这样的在文章前后表达上的不一致？

动态规划问题的思路总结：第一步：如果待解决的问题为func（n），自己可以假设func（n-1）、func（n-2）……func（1）都已经解出，然后就是如何利用这些结果来推导出func（n），经过这么分析就可以得出推导方程。第二步：设计dp数组来保存func（n）（一维数组、二维数组等）。第三步：从0开始遍历，按照状态转移方程计算出func（n）保存到dp数组
举例，以下这些leetcode动态规划相关的题都可以直接套用这个解题思路

一维dp数组的题目
322. Coin Change
121. Best Time to Buy and Sell Stock
53. Maximum Subarray
300. Longest Increasing Subsequence
152. Maximum Product Subarray

二维dp数组的题目
152. Maximum Product Subarray
120. Triangle

第二遍学习，看留言有同学不理解状态转移表的填充过程，现总结一下状态转移表的填充详细过程和对应的字符编辑操作，望老师指正：
1 minDist[i][j]表示处理完a[i]和b[j]时（a[0...i]已全部转换到b[0...j]），需要的最小编辑次数
2 a[i]和b[j]不相等时，状态转移公式为：minDist[i][j]=min(minDist(i-1,j)+1, minDist(i,j-1)+1，minDist(i-1,j-1))
   1) 如果minDist[i][j]=minDist(i-1,j)+1，现分析一下这个状态转移的具体过程。minDist(i-1,j)表示a[0...i-1]已全部转换到b[0...j]，如何编辑字符才能从minDist(i-1,j)到达minDist[i][j]这个状态呢？要么将a[i]这个字符删除，要么在b[j]后边添加一个跟a[i]相同的字符（这里编辑的操作跟老师讲的回溯法的操作是不一样的）
   2）如果minDist[i][j]=minDist(i-1,j-1)，现分析一下这个状态转移的具体过程。如何编辑字符才能从minDist(i-1,j-1)到达minDist[i][j]这个状态呢？？将a[i]替换为b[j]或者将b[j]替换为a[i]即可
  3) 如果minDist[i][j]=minDist(i,j-1)+1，跟上边第一种情况类似
3 a[i]和b[j]相等时比较简单，不需要做字符的编辑

思考题的解法还是很精妙的
递推公式:
a[0...i] 的最长子序列为: a[i] 之前所有比它小的元素中子序列长度最大的 + 1

代码实现:
```
#include<iostream>

using namespace std;

// 动态规划求 a 的最上升长子序列长度
#include<iostream>

using namespace std;

// 动态规划求 a 的最上升长子序列长度
int longestSubsequence(int *a, int n) {
    // 创建一个数组, 索引 i 对应考察元素的下标, 存储 arr[0...i] 的最长上升子序列大小
    int *lss_lengths = new int[n];
    // 第一个元素哨兵处理
    lss_lengths[0] = 1;
    // 动态规划求解最长子序列
    int i, j, max;
    for (i = 1; i < n; i++) {
        // 计算 arr[0...i] 的最长上升子序列
        // 递推公式: lss_lengths[i] = max(condition: j < i && a[j] < a[i] value: lss_lengths[j] + 1)
        max = 1;
        for (j = 0; j < i; j++) {
            if (a[i] > a[j] && lss_lengths[j] >= max) {
                max = lss_lengths[j] + 1;
            }
        }
        lss_lengths[i] = max;
    }
    int lss_length = lss_lengths[n - 1];
    delete[]lss_lengths;
    return lss_length;
}

void main() {
    const int n = 7;
    int arr[n] = { 2, 9, 3, 6, 5, 1, 7 };;
    cout << longestSubsequence(arr, n) << endl;
    getchar();
}

思考题java版解答：
public int longestIncreaseSubArrayDP(int[] array) {
    if (array.length < 2) return array.length;
    int[] state = new int[array.length];
    state[0] = 1;
    for (int i = 1; i < state.length; i++) {
        int max = 0;
        for (int j = 0; j < i; j++) {
            if (array[j] < array[i]) {
                if (state[j] > max) max = state[j];
            }
        }
        state[i] = max + 1;
    }
    int result = 0;
    for (int i = 0; i < state.length; i++) {
        if (state[i] > result) result = state[i];
    }
    return result;
}

老师我有个疑问（急），希望老师能够帮忙回答下，这也是大部分留言中没能解决的疑问。
在莱文斯坦距离讲解时，那里的状态方程是怎么直接写出来的？这一点是我最不能理解的，当然在问该问题之前，我已经尽我所能的尝试理解老师的文章，并且把留言也都翻了一遍。老师请看我下面的陈述：

一：按照老师文章的讲解顺序，先分析了如何用回溯方法，然后绘制了递归树，从递归树中又分析出了具有重复的子结构，接着又画出了状态简图（递归树下面的图，不知道怎么表达），从这幅简图中清晰的看出来状态的转移方式，接下来重点来了！！！文章接着就写出来状态转移方程（不理解的地方）！我在留言中发现，老师对这点的解释是说「状态转移方程与递归树无关，递归树仅仅表达了问题具有重复子结构」，如果按照老师的说法，不根据递归树分析出状态转移过程，那该怎么直接写出状态转移方程（要能够合理的推断出来，而不是靠经验，否则还是无法掌握动态规划）？目前来看，我在文章中没有发现具有这样的逻辑推断。我之前的理解是说，我们其实可以在递归树中分析出状态转移方程如何写，然后这样就形成了一个闭环，由回溯->递归树->状态转移方程。希望在这里老师能够给出一个合理的解释？

二：抛开上面的一些问题，咱们单独看莱问斯坦距离状态转移公式，先假设，按照递归树和递归树下面的图可以知道状态转移的过程（这是一个前提假设）。在留言中的第 4 条「blacknhole」这位同学的留言中，我也有相同的疑问，(i , j, min_edist) 到底表达的是什么状态？（处理完 a[i] b[j] 后的最小距离？ or 刚要处理 a[i] b[j] 时对应的最小距离？），

接下来按照二种不同的表达来看看状态方程如何推断出来：

1、 如果表达的含义是 「处理完 a[i] b[j] 后的最小距离」

那么其实从回溯算法中可以知道（因为 i j 的前一个状态已经处理完了，比如 min_edist(i-1,j) 就代表了前一个状态。）

if (a[i] != b[j])

​    min_edist(i, j) =1+ min( min_edist(i-1, j), min_edist(i, j-1), min_edist(i-1,j-1))

if (a[i] == b[j] )

​    min_edist(i, j) = min( min_edist(i-1, j), min_edist(i, j-1), min_edist(i-1,j-1))

2、如果表达的含义是「刚要处理 a[i] b[j] 时对应的最小距离」

那么我们可以这么想，当前 i,j min_edist 表示还没有处理过 i,j 时对应的状态，因此我们需要考虑之前的状态是怎么传递到这里来的

min_edist(i, j) =

min(min_edist(i-1,j)+1, min_edist(i, j-1)+1, min_edist(i-1, j-1) + (a[i-1] == b[j-1]? 0 : 1))



从上面的两种推断发现，我觉的都是比较合理的，但是没有一种的结果与老师给的状态转移方程是一致的（这一点比较疑惑）？所以对于老师的状态转移方程肯定不是从递归树中直接推导出来的，那么请问老师这个状态转移方程该怎么合理的推断出来（我觉得这个问题不是靠多做题解决的，必须要知道推理逻辑才能彻底掌握动态规划）？



三：接下来还有一个问题（前提假设是老师的状态方程是正确的，具体逻辑还不能理解）

那么如果根据状态状态方程，来填充状态表的第 0 行 第 0列呢（留言中也有许多这方面的疑问）？按照我的理解，既然状态转移方程我们知道了，那么其实从状态转移方程中就可以直接填充表格了，比如填充第 0 行时，因为从状态转移方程中我们发现有 i - 1,j-1 因此当计算第 0 行时，带有 i-1 项的就可以省略了，因此状态转移方程就剩下 (i, j-1) 项了。然后其实就不用分 a[i] b[j] 是否相等了，但是回头看老师的代码，却不明白为什么还要分 a[i] b[j] 相等不相等。希望老师能够解释一下！



综上：如果老师觉得我描述的问题不清楚，那么希望老师看看这篇文章的其他问题留言，总结一下大家到底哪里不理解，并且对不理解的地方从新更新下当前文章，具体解释一下，比如老师在留言中说过「不能从递归树中直接推导出状态转移方程，两者没有联系」，那么希望老师在文章的对应地方直接表明这句话，并且在加上额外的说明，比如如何推断出状态转移方程，这样整篇文章才能让更多的人从本质上理解动态规划！



最后希望老师能够认真给出我上面几个问题的解答，谢谢老师！

莱温斯坦距离状态表，初始化第0行和第0列代码逻辑有点复杂，可以简化一下，修改状态表为如下形式
    ∅    m    t    a    c    n    u
∅    0    1    2    3    4    5    6
m    1    0    1    2    3    4    5
i    2    1                    
t    3    2                    
c    4    3                    
m    5    4                    
u    6    5                    
代码就可以简化了
int[][] minDist = new int[n+1][m+1]
  for (int j = 0; j <= m; ++j) { 初始化第0行
    minDist[0][j] = j;
  }
  for (int i = 0; i <= n; ++i) { 初始化第0列
    minDist[i][0] = i;
  }
最终return minDist[n][m];

思考题解答：
状态转移公式：maxLen[i] = max(maxLen[j]+(1 if j<i else 0)) for any j < i
python代码：
def maxOrderedSeq(seq):
    maxLen = [1] * len(seq) # 初始化为1
    
    for i in range(1, len(seq)): # i从1开始
        for j in range(i-1,-1,-1): # j从i-1到0
            if seq[j] <= seq[i]:
                maxLen[i] = maxLen[j] + 1
                break # 满足则退出
        if maxLen[i] == 1: # 比前面所有元素小
            maxLen[i] = maxLen[i-1]
            
    print(maxLen)
            
# usage
seq = [2, 9, 3, 6, 5, 1, 7]
maxOrderedSeq(seq)

为什么到后面留言这么少？

在编辑距离里面， 状态转移方程，第二种case ,是不是可以改为：

如果：a[i]==b[j]，那么：min_edist(i, j) 就等于：min_edist(i-1,j-1)

a[i]==b[j]
a[0..i] 和 b[0..j] 的编辑距离就等价于 a[0..i-1] 和 b[0..j-1]的编辑距离
    

思考题就是 leetcode 300 题：https://leetcode-cn.com/problems/longest-increasing-subsequence/submissions/

public int minSubsequence(int[] array) {
        if(array.length <2) return array.length;
        int[] dp = new int[array.length];
        // dp[i] 是以 array[i] 结尾的最长子序列
        Arrays.fill(dp,1);
        for(int i = 0; i< array.length; i++) {
            for(int j = 0; j< i; j++) {
                if(array[i] > array[j]) {
                    dp[i] = Math.max(dp[i],dp[j] +1);
                }
            }
        }
        int res = 0;
        for(int i = 0; i< dp.length; i++) {
            res = Math.max(res,dp[i]);
        }
        return res;
    }