最长上升子序列——回溯法
什么是最长上升子序列
回溯法其实算是一种暴力法,但是我们必须先学会暴力法再去考虑更优化的算法,不然真的会。。。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); } }
思路很清晰!