共计 3782 个字符，预计需要花费 10 分钟才能阅读完成。
读完本文，你能够去力扣拿下如下题目：
300. 最长回升子序列
———–
兴许有读者看了前文 动静布局详解，学会了动静布局的套路：找到了问题的「状态」，明确了 dp 数组 / 函数的含意，定义了 base case；然而不晓得如何确定「抉择」，也就是不到状态转移的关系，仍然写不出动静布局解法，怎么办？
不要放心，动静布局的难点原本就在于寻找正确的状态转移方程，本文就借助经典的「最长递增子序列问题」来讲一讲设计动静布局的通用技巧：数学演绎思维。
最长递增子序列（Longest Increasing Subsequence，简写 LIS）是十分经典的一个算法问题，比拟容易想到的是动静布局解法，工夫复杂度 O(N^2)，咱们借这个问题来由浅入深解说如何找状态转移方程，如何写出动静布局解法。比拟难想到的是利用二分查找，工夫复杂度是 O(NlogN)，咱们通过一种简略的纸牌游戏来辅助了解这种奇妙的解法。
先看一下题目，很容易了解：
留神「子序列」和「子串」这两个名词的区别，子串肯定是间断的，而子序列不肯定是间断的。上面先来设计动静布局算法解决这个问题。
一、动静布局解法
动静布局的外围设计思维是数学归纳法。
置信大家对数学归纳法都不生疏，高中就学过，而且思路很简略。比方咱们想证实一个数学论断，那么 咱们先假如这个论断在 k<n 时成立，而后依据这个假如，想方法推导证实出 k=n 的时候此论断也成立。如果可能证实进去，那么就阐明这个论断对于 k 等于任何数都成立。
相似的，咱们设计动静布局算法，不是须要一个 dp 数组吗？咱们能够假如 dp[0...i-1] 都曾经被算进去了，而后问本人：怎么通过这些后果算出 dp[i]？
间接拿最长递增子序列这个问题举例你就明确了。不过，首先要定义分明 dp 数组的含意，即 dp[i] 的值到底代表着什么？
咱们的定义是这样的：dp[i] 示意以 nums[i] 这个数结尾的最长递增子序列的长度。
PS：为什么这样定义呢？这是解决子序列问题的一个套路，后文动静布局之子序列问题解题模板 总结了几种常见套路。你读完本章所有的动静布局问题，就会发现 dp 数组的定义方法也就那几种。
依据这个定义，咱们就能够推出 base case：dp[i] 初始值为 1，因为以 nums[i] 结尾的最长递增子序列起码要蕴含它本人。
PS：我认真写了 100 多篇原创，手把手刷 200 道力扣题目，全副公布在 labuladong 的算法小抄，继续更新 。倡议珍藏， 依照我的文章程序刷题，把握各种算法套路后投再入题海就蛟龙得水了。
举两个例子：
算法演进的过程是这样的，：
依据这个定义，咱们的最终后果（子序列的最大长度）应该是 dp 数组中的最大值。
int res = 0;
for (int i = 0; i < dp.size(); i++) {res = Math.max(res, dp[i]);
}
return res;读者兴许会问，方才的算法演进过程中每个 dp[i] 的后果是咱们肉眼看进去的，咱们应该怎么设计算法逻辑来正确计算每个 dp[i] 呢？
这就是动静布局的重头戏了，要思考如何设计算法逻辑进行状态转移，能力正确运行呢？这里就能够应用数学演绎的思维：
假如咱们曾经晓得了 dp[0..4] 的所有后果，咱们如何通过这些已知后果推出 dp[5] 呢？
依据方才咱们对 dp 数组的定义，当初想求 dp[5] 的值，也就是想求以 nums[5] 为结尾的最长递增子序列。
nums[5] = 3，既然是递增子序列，咱们只有找到后面那些结尾比 3 小的子序列，而后把 3 接到最初，就能够造成一个新的递增子序列，而且这个新的子序列长度加一。
显然，可能造成很多种新的子序列，然而咱们只抉择最长的那一个，把最长子序列的长度作为 dp[5] 的值即可。
for (int j = 0; j < i; j++) {if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}当 i = 5 时，这段代码的逻辑就能够算出 dp[5]。其实到这里，这道算法题咱们就根本做完了。
读者兴许会问，咱们方才只是算了 dp[5] 呀，dp[4], dp[3] 这些怎么算呢？相似数学归纳法，你曾经能够算出 dp[5] 了，其余的就都能够算进去：
for (int i = 0; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}联合咱们方才说的 base case，上面咱们看一下残缺代码：
public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];
// base case：dp 数组全都初始化为 1
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[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;
}至此，这道题就解决了，工夫复杂度 O(N^2)。总结一下如何找到动静布局的状态转移关系：
1、明确 dp 数组所存数据的含意。这一步对于任何动静布局问题都很重要，如果不得当或者不够清晰，会妨碍之后的步骤。
2、依据 dp 数组的定义，使用数学归纳法的思维，假如 dp[0...i-1] 都已知，想方法求出 dp[i]，一旦这一步实现，整个题目根本就解决了。
但如果无奈实现这一步，很可能就是 dp 数组的定义不够失当，须要从新定义 dp 数组的含意；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，须要把 dp 数组扩充成二维数组甚至三维数组。
PS：我认真写了 100 多篇原创，手把手刷 200 道力扣题目，全副公布在 labuladong 的算法小抄，继续更新 。倡议珍藏， 依照我的文章程序刷题，把握各种算法套路后投再入题海就蛟龙得水了。
二、二分查找解法
这个解法的工夫复杂度为 O(NlogN)，然而说实话，正常人根本想不到这种解法（兴许玩过某些纸牌游戏的人能够想进去）。所以大家理解一下就好，失常状况下可能给出动静布局解法就曾经很不错了。
依据题目的意思，我都很难设想这个问题居然能和二分查找扯上关系。其实最长递增子序列和一种叫做 patience game 的纸牌游戏无关，甚至有一种排序办法就叫做 patience sorting（急躁排序）。
为了简略起见，后文跳过所有数学证实，通过一个简化的例子来了解一下算法思路。
首先，给你一排扑克牌，咱们像遍历数组那样从左到右一张一张解决这些扑克牌，最终要把这些牌分成若干堆。
解决这些扑克牌要遵循以下规定：
只能把点数小的牌压到点数比它大的牌上；如果以后牌点数较大没有能够搁置的堆，则新建一个堆，把这张牌放进去；如果以后牌有多个堆可供选择，则抉择最右边的那一堆搁置。
比如说上述的扑克牌最终会被分成这样 5 堆（咱们认为纸牌 A 的牌面是最大的，纸牌 2 的牌面是最小的）。
为什么遇到多个可抉择堆的时候要放到最右边的堆上呢？因为这样能够保障牌堆顶的牌有序（2, 4, 7, 8, Q），证实略。
依照上述规定执行，能够算出最长递增子序列，牌的堆数就是最长递增子序列的长度，证实略。
咱们只有把解决扑克牌的过程编程写进去即可。每次解决一张扑克牌不是要找一个适合的牌堆顶来放吗，牌堆顶的牌不是 有序 吗，这就能用到二分查找了：用二分查找来搜寻以后牌应搁置的地位。
PS：旧文二分查找算法详解具体介绍了二分查找的细节及变体，这里就完满利用上了，如果没读过强烈建议浏览。
public int lengthOfLIS(int[] nums) {int[] top = new int[nums.length];
// 牌堆数初始化为 0
int piles = 0;
for (int i = 0; i < nums.length; i++) {
// 要解决的扑克牌
int poker = nums[i];
/***** 搜寻左侧边界的二分查找 *****/
int left = 0, right = piles;
while (left < right) {int mid = (left + right) / 2;
if (top[mid] > poker) {right = mid;} else if (top[mid] < poker) {left = mid + 1;} else {right = mid;}
}
/*********************************/
// 没找到适合的牌堆，新建一堆
if (left == piles) piles++;
// 把这张牌放到牌堆顶
top[left] = poker;
}
// 牌堆数就是 LIS 长度
return piles;
}至此，二分查找的解法也解说结束。
这个解法的确很难想到。首先波及数学证实，谁能想到依照这些规定执行，就能失去最长递增子序列呢？其次还有二分查找的使用，要是对二分查找的细节不分明，给了思路也很难写对。
所以，这个办法作为思维拓展好了。但动静布局的设计办法应该齐全了解：假如之前的答案已知，利用数学演绎的思维正确进行状态的推演转移，最终失去答案。
_____________
我的 在线电子书 有 100 篇原创文章，手把手带刷 200 道力扣题目，倡议珍藏！对应的 GitHub 算法仓库 曾经取得了 70k star，欢送标星！
