• 题目
  • 思路，粗暴的递归动态规划解法
    • 做题时的全部思路，是一边做一边写的。
    • 代码
  • 俺的一些话

题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路，粗暴的递归动态规划解法

做题时的全部思路，是一边做一边写的。

• 这里的思路全是我做题时写的，可以清楚看出我是怎么得出结果的，感觉应该有帮助，所以就直接CV出来了。

• 如果只想看题解的思路的话，直接看代码吧，我会用注释详细说明的。

• //1.当i+1>i的时候，递增子序列的个数+1，且此时子序列的最小值为i+1

• //2.题目就是，选取限定范围内，大于n的最小值，一共选取的次数，就是子序列的长度

• //3.则需要的状态有，上一个最小值，此时的最小值，此时子序列的长度

• //当i大于此时的最小值，长度+1，最小值为i。

• //当i<此时的最小值，大于上一个最小值，则i为最小值，长度不变

• //直到找到最后的数字，输出长度。

• //出错了，第一个数字开头不一定是最好的，所以得对每个开头都尝试一遍

• //然后对比彼此的最长子序列，看哪个大输出哪个

• //那么现在要思考的就是，要怎么剪枝？

• //1.当最大值小于当前最大值后，就可以不必再计算这个数字开头了

• //2.对每一个数字，记录使用该数字时的最大子序列长度。若下一次长度小于该长度，就可以不必再计算了

• //再一次出错了，可能会出现这种情况，0...18个大于1的数字...1.2.5

• //这样子的话，我原本的算法只对当前的两位数字进行了比较，就无法跳到那么后面了。

• //果然还是用回传统的方式比较好吗

• //也就是，对每个数字的每种可能都进行运算，然后对比得出最大值。

• //运算函数。

• //给出初始值，算出该初始值的最大子序列

• //对每个数字为初始值计算一次

• //对比得出最大子序列然后输出.

• //算最大子序列的逻辑

• //初始值为i的最大子序列，等于1+x的最大子序列。(x>i且x的排序在i后面)

• //若x为空，则最大子序列为1。

• //下一个问题，怎么得出最大子序列，现在这样只是得出了子序列罢了，返回的也只是最后的子序列，而非最大子序列

• //显而易见的，当前少了比较，得出最大值的一步。

• //那么要怎么写呢？

• //在可以得到子序列的情况下，对比一下不同子序列的大小，即可得出最大值。

• //然后返回最大值

• //下一步，还是剪枝，用上面的那个思想的话，“对每一个数字，记录使用该数字时的最大子序列长度。若下一次长度小于该长度，就可以不必再计算了”

• //这一步，该放在哪里？目前可以得知，应该是在计算用新的初始值计算的时候，进行判断。

• //储存的是到达指定数字时的最大子序列，所以怎么找到到达该数字时的子序列，然后进行对比？

• //按原本的思路的话，是1+1+1...一直加到结束，然后总结，得出初始值的最大子序列

• //根本得不到到该数字时的子序列，得到的只会是最大子序列，所以得改变思路。

• //新思路，递推。

• //设置一个 n 值，用于保存到达该初始值时的最大子序列，

• //n 为全局变量，每次循环都会调用并+1，那么在函数进行时，n的值便是当前数字的子序列

• //对比该数字的最大子序列，就可以进行剪枝了

• //需要注意的是，为了避免 n 的值只增不减，记得做回溯操作，在循环调用函数的时候，调用完了，就给n-1

• //其实我想做的是，仅递推的，但又想不出来怎么做，只好接着递归，然后用n值来剪枝了

• //运算函数这就算写好了，那下一步就是主函数了

• //主函数需要有的内容是，对每个数字作为初始值来运算，找到最大的那个

• //那用循环就行了吧？应该是，我试试。

• //奇了怪了，明明特意做了剪枝操作，却还是超出时间限制。

• //那一是剪枝做的不够好，二是这剪枝有问题，做了等于没做。

• //先假设是第二个问题，剪枝有问题，做了等于白做，找下bug看看

• //首先删去剪枝，对比一下结果有没有问题

• //啧，剪枝没问题，能正常使用，那就是第一个问题了，效率不够好，还得找更优解

代码

int lengthOfLIS(int* nums, int numsSize){


int jj,n=1,max=0,localmax[3000]={0};
//jj的作用看下面的循环，n用于剪枝，max用于存储最大值，localmax用于存储指定数字的最大子序列
int yunsuan(int p,int m)//p是初始值，m是p在数组中的下标
{
    if(n>localmax[m])   //若n>指定下标的最大值,使得指定下标的最大值为n，否则结束函数.
    {
        localmax[m]=n;
    }
    else
    {
        return 0;
    }
    int x=0,da=0;
    for(int i=m+1;i<numsSize;i++)	//从当前下标+1开始，对每个数字进行计算
    {
        if(nums[i]>p)	//若该数字大于原数值
        {
            n++;	//储存n值，用于剪枝
            x=1+yunsuan(nums[i],i);	//则递归运算，当前子序列等于1+剩余的子序列
            if(x>da)	//若计算结果 x 为更大值
            {
                da=x;	//则对最大值 da 赋值计算结果 x
            }
            n--;	//回溯n值
        }
    }
    return da;	//返回最大值（最大子序列）
}
for(int i=0;i<numsSize;i++)	//把每个数字当做初始值，进行运算
{
    jj=1+yunsuan(nums[i],i);	//用jj储存运算结果
    if(jj>max)	//比较运算结果 jj 和最大值 max
    {
        max=jj;
    }
}
return max;	//最后输出 x 值。就算做完了。
}

俺的一些话

其实这个做法过不过得看运气，我第一次提交超时了，第二次提交却过了
哎嘿嘿，真幸运。(～￣▽￣)～
过两天我再做个更优解试试。ヾ(o´∀｀o)ﾉ
现在就这样将就着用吧，啦啦啦~

哦对了，这题我是在力扣上做的，所以详细的过程或许会有点偏差，不过思路应该都是通用的啦。就这样了，拜了个拜~