最长上升子序列——回溯法

什么是最长上升子序列

回溯法其实算是一种暴力法，但是我们必须先学会暴力法再去考虑更优化的算法，不然真的会。。。boom

不能交叉，所以你从一边开始遍历的时候，另一边被匹配的点只会一次比一次高。所以只需要记录下被匹配那一边的index就好了。

(我们这题是修路的例子，也是一样的)

回溯法思路

如果这个位置接下去搜索不到
弃掉
如果这个位置接下去搜索得到
可以选择匹配
也可以不匹配

先判断回溯条件

if (b == n || a == n) {

    max = Math.max(max, sum);
    return;

}

寻找循环

int newIndex = -1;

boolean flag = false;
for (int i = b; i < n; i ++) {

    //如果找得到,可以连也可以不连
    if (first[a] == second[i]) {


        newIndex = i;
        
        flag = true;
        break;

    }

}

如果这个位置接下去搜索不到
弃掉

//如果找不到
if (!flag) {

    //继续找下一个a，b不增加，sum不增加
    back(a + 1, b, sum);

如果这个位置接下去搜索得到
可以选择匹配

也可以不匹配

else {

    for (int i = 0; i < 2; i ++) {

        //选择连
        if (i == 0) {

            back(a + 1, newIndex + 1, sum + 1);

            //不选择连
        } else {

            back(a + 1, b, sum);

        }

    }

思路很清晰!