最长的递增子序列--动态规划、递归

问题简述

对于一个数组，计算其中最长的递增子序列的长度，并输出。

主要思路如下：

代码中提供了三种不同的实现方法：纯递归、递归+动态规划（记忆化），以及纯动态规划（迭代）。下面是每种方法的主要思路：

1. 纯递归实现（dp方法）

这个方法尝试通过递归找到以每个元素结尾的最长递增子序列的长度。对于每个元素，它会比较后续所有元素，如果找到比当前元素大的元素，就增加计数。但是，这个方法有几个问题：

• 它没有正确地返回递归调用的结果，导致递归的结果丢失。
• 它没有正确地利用递归的性质来避免重复计算。

2. 递归+动态规划（记忆化）实现（dp2方法）

这个方法是对第一种方法的优化，它使用一个数组get来存储每个位置的最长递增子序列的长度，从而避免重复计算。主要思路如下：

• 使用一个数组get来存储每个位置的最长递增子序列的长度。
• 在递归之前，先检查get[j]是否已经被计算过，如果是，则直接返回该值。
• 如果get[j]没有被计算过，那么递归地计算以nums[j]为起点的最长递增子序列的长度，并存储在get[j]中。
• 在所有递归调用结束后，遍历get数组找到最大值，即为整个数组的最长递增子序列的长度。

3. 动态规划（迭代）实现（dp3方法）

这个方法使用迭代而不是递归来计算最长递增子序列的长度。主要思路如下：

• 创建一个数组get，用于存储每个位置的最长递增子序列的长度。
• 从数组的末尾开始向前遍历，对于每个元素，检查其后面所有元素是否比当前元素大，如果是，则更新get[i]的值。
• 在遍历结束后，遍历get数组找到最大值，即为整个数组的最长递增子序列的长度。

package Dp;
/*
* 实现一个最长的递增子序列的计算，递归实现,递归+动态规划实现，动态规划实现
* */


public class LongestLCR {
    //递归的实现
    public static int dp(int [] nums,int j,int max){
        //递归的出口
        if(j == nums.length - 1){
            return 1;
        }

        int count = 1;//记录个数
        int pre = nums[j];

        for(int i = j ; i < nums.length; i++){
            if(nums[i] >  pre){
                count ++;
                pre = nums[i];
            }
        }

        max = Math.max(max,count);
        dp(nums,j + 1, max);

        //最终的返回值
        return max;
    }


    //递归形式的动态规划，进行一次优化
    public static int dp2(int[] nums, int j ,int[] get){
        //首先判断该处的最大长度是否已经进行存储
        if(get[j] != 0){
            return get[j];
        }

        //递归的出口
        if(j == nums.length - 1){
            return 1;
        }

        //还是进行递归，不同的是，所有j开始的结果都记录在get数组中，减少了相同的计算
        int maxlen = 1;
        for(int i = j + 1; i < nums.length; i++){
            if(nums[i] > nums[j]){
                maxlen  = Math.max(maxlen , dp2(nums,i,get) + 1);
            }
        }
        get[j] = maxlen;

        int result = 0;
        for (int i = 0; i < get.length; i++) {
            if(get[i] > result){
                result = get[i];
            }
        }

        return result;
    }

    //使用动态规划，但是使用迭代，不再使用递归
    public static int dp3(int[] nums){
        int result = 0;
        int[] get = new int[nums.length];

        //从尾部进行遍历,并记录每一个开始位置的结果
        for (int i = nums.length - 1; i >= 0 ; i--) {
            //记录每一个位置的结果
            get[i] = 1;
            //进行每一个位置的计算
            for(int j = i + 1; j < nums.length ; j ++){
                if(nums[j] > nums[i]){
                    get[i] = Math.max(get[i],get[j] + 1);
                }
            }
        }

        for (int j : get) {
            if (result < j) {
                result = j;
            }
        }
        return result;
    }


    public static void main(String[] args) {
        int[] array = new int[]{1, 4, 3, 2,5};
        System.out.println(
                "第一种方式的结果是：" + dp(array,0,0)
        );

        System.out.println(
                "第二种方式的结果是：" + dp2(array,0,new int[array.length])
        );

        System.out.println(
                "第三种方式的结果是：" + dp3(array)
        );
    }
}

总结

这三种方法都是用来解决最长递增子序列问题，但是它们的效率和实现方式不同。第一种方法效率较低，因为它没有避免重复计算，时间复杂度是指数级，一旦数据量增多，太慢了。第二种方法通过记忆化减少了重复计算，计算快了很多倍。第三种方法则是最常用的动态规划方法，它避免了递归调用的开销，通常也是效率最高的，这里只是输出了最长的递增子序列的长度，感兴趣的uu们可以思考下怎么输出对应的最长的递增字符串，假使只有一个最长递增子序列。