DP四大问题总结之最长递增子序

Dynamic Programming

Posted by Jerry on February 18, 2017

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划

Dynamic Programming

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。与分治法类似,基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将结果记录下来,方便之后使用。这就是动态规划法的基本思路.

DP适用条件

  1. 最优化原理(最优子结构性质) 最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
  2. 无后效性 将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。
  3. 子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。

动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。

状态转移方程:给定k阶段状态变量x(k)的值后,如果这一阶段的决策变量一经确定,第k+1阶段的状态变量x(k+1)也就完全确定,即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化,那么可以把这一关系看成(x(k),u(k))x(k+1)确定的对应关系,用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律,也就是状态转移方程。

最长递增子序 (Longest increasing subsequence)

问题描述

设有由n个不相同的整数组成的数列,记为:a[0]、a[1]、……、a[n-1]且a(i)<>a(j) (i<>j),若存在i1<i2<i3< … < ie且有a[i1]<a[i2]< … <a[ie]则称为长度为e的递增子序列序列。例如{2,3,4,17,2,18,10,15,16},其中{2,3,4,17,18}是长度5的递增子序,而{2,3,4,10,15,16}是长度为6的递增子序,显然这里的最长递增子序为后者。

求解算法

  1. 用暴力算法解决的话时间复杂度为O(2n),原因在于长度为n的数组,可能有2n个子序列。

  2. 用动态规划算法时间复杂度为O(n2),空间复杂度为O(n)

  3. 维护一个数组MaxV[i],记录长度为i的递增子序列中最大元素的最小值,并对于数组中的每个元素考察其是哪个子序列的最大元素,二分更新MaxV数组,最终i的值便是最长递增子序列的长度。时间复杂度O(n*log(len)),空间复杂度O(len),len为最长递增子序的长度。

代码实现

public class Solution{
    public int LIS(int[] nums){
        if(nums==null)return 0;
        int[] dp = new int[nums.length];
        for(int i=0;i<nums.length;i++)
            //初始化dp中每个元素的LIS最少为1
            dp[i] = 1;
        int ans = 0;
        for(int i = 0;i<nums.length;i++){
            for(int j = i-1;j>=0;j--){
                //如果满足当前nums[i]比nums[j]大,且dp中元素要小,则更新dp值
                if(nums[i]>nums[j]&&dp[i]<dp[j]+1){
                    dp[i]=dp[j]+1;
                    if(dp[i]>ans)ans = dp[i];
                }
            }
        }
        return ans;
    }

    public  int LIS2(int[] nums){
        int[] max = new int[nums.length];
        int len = 1;
        max[0] = nums[0];
        for(int i = 1;i<nums.length;i++){
            if(nums[i]>max[len-1]){
                //长度加一
                max[len++] = nums[i];
            }else{
                //找到要更新的位置,将大的值替换成较小的值,但len的长度不变
                int pos = BinarySearch(max,0,len-1,nums[i]);
                max[pos] = nums[i];
            }
        }
        for(int i=0;i<len;i++){
            System.out.print(max[i] + " ");
        }
        System.out.println();
        return len;
    }
    
    /**
     * 上面的代码这样描述会更好理解一点:

     开一个数组max,下标为0的位置设置为data[0],对于从1开始的每一位元素,

     如果大于max数组最后一个位置的元素,则max数组长度增1,设置为当前的这个元素

     如果不大于max数组最后一个位置的元素,则从max的最后一个元素开始往前找,替换第一个大于当前元素的那个值。

     这样,最终max数组的长度就是最长递增子序列的长度。

     算法的时间复杂度是O(n*log(len)),其中len是递增子序列的最大长度。
     */

    private int BinarySearch(int[] nums, int low, int high, int target) {
        while(low<=high){
            int mid = (low+high)/2;
            if(nums[mid]<=target){
                low = mid+1;
            }else {
                high = mid-1;
            }
        }
        return low;
    }
}

参考资料

  1. http://m.blog.csdn.net/article/details?id=51228468
  2. http://blog.csdn.net/imzoer/article/details/8100064
  3. 百度百科