二分法和动态规划
题目
给定一个无序的整数数组，找到其中最长上升子序列的长度。
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
动态规划
1.概念：动态规划就是把一个大问题拆成一个个小问题(分治思想)，但是动态规划的核心并不在此，而是那些小问题会不会被复用。
1) 举个简单的例子：在纸上写上1+1+1，问它的和是多少，都知道是1+1+1=3，之后在1+1+1之前再写上一个1+，问它的和，这时候有两种计算方法，第一种是1+1+1+1=4,而另一种方法是1+3=4，因为之前我们已经计算了1+1+1了，就无需再次计算了，这就是动态规划。
2) 走楼梯的例子：有n级台阶，人只能一次走1级或者2级，问这个人有多少种走法？
f(1)=1,第一次只能跳一级；f(2)=2,第二次可以跳一级或者两级；第三次f(3)=f(2)+f(1),即如果第一次跳一格，那么有f(2)种跳法，第一次跳两格，那么就f(1)次跳法，由此类推f(n)=f(n-1)+f(n-2);
二分法
1.概念：在用二分法进行查找时，查找对象的数组必须是有序的，即各数组元素的次序是按其值的大小顺序存储的。其基本思想是先确定待查数据的范围（可用 [left,right] 区间表示），然后逐步缩小范围直到找到或找不到该记录为止。具体做法是：先取数组中间位置（mid=(left+right)/2）的数据元素与给定值比较。若相等，则查找成功；否则，若给定值比该数据元素的值小（或大），则给定值必在数组的前半部分[left,mid-1]（或后半部分[mid+1,right]），然后在新的查找范围内进行同样的查找。如此反复进行，直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为止。因此，二分查找每查找一次，或成功，或使查找数组中元素的个数减少一半，当查找数组中不再有数据元素时，查找失败。
2.例子：编写一个计算x的平方根的程序，x保证为正数，求：5的平方根：
思路：设f(x)=x2,f(x)随x的增大而增大，所以我们采取二分法，首先，我们令mid = (left+right)/2,用mid的平方与5比较:
1) f(mid)>5,令right=mid；
2) f(mid)<5,令left=mid;
题目解析
1.动态规划解题
解题思路：
状态定义：dp[i]代表前i个数字的最长序列长度
转移思想：设j∈[0,i)，考虑每轮计算新 dp[i]时，遍历[0,i)列表区间，做以下判断:
1) num[i]>num[j]时，num[i]可以接在num[j]之后，此情况下最长上升子串dp[i]=dp[j]+1
2) num[i]<num[j]时，num[i]不可以接在num[j]之后，跳过
执行方程：dp[i]=max(dp[i],dp[j]+1)
代码如下：
private int lengthOfLIS(int[] nums) {
if(nums.length == 0){
return 0;
}
int[] dp = new int[nums.length];
int res = 0;
Arrays.fill(dp,1);
for(int i=0;i<nums.length;i++){
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
res = Math.max(res,dp[i]);
}
return res;
} 2.动态规划+二分法解题
思路：主要问题是如何降低时间复杂度：
1.动态规划中，通过线性遍历来计算dp的复杂度O(n)无法降低
2.需要通过线性遍历[0,k)区间元素来得到，我们可以通过重新定义状态，使整个列表变成一个顺序列表，这样在计算每个 dp[k]dp[k]dp[k] 时，就可以通过二分法遍历[0,k)区间元素，将此部分复杂度由O(N)降至 O(logN)
代码：
private int lengthOfLIS1(int[] nums) {
int[] tails = new int[nums.length];
int res = 0;
for(int num : nums) {
int i = 0, j = res;
while(i < j) {
int m = (i + j) / 2;
if(tails[m] < num) i = m + 1;
else j = m;
}
tails[i] = num;
if(res == j) res++;
}
return res;
}
