LeetCode 300. 最长递增子序列 题解（C,C++） （包含动态规划与贪心的区别的资料）

题目链接： - 力扣（LeetCode）

资源：

关于动态规划和贪心算法的区别，动态规划的常见题型，我总结了一些（还有文档哦，持续更新，以后有扩充），大家可移步至：动态规划知识点

C代码：

//动态规划做题重要的五步：1.确定dp数组的含义和下标的含义    2.确定递推公式  3.知道递推公式了，就要想如何初始化
//4.确定遍历顺序  5.打印数组

//注意是严格递增！！！！！！

int max(int a, int b)
{
    return a > b ? a : b;
}

int lengthOfLIS(int* nums, int numsSize) 
{
    //如果一个元素都没有，就直接返回0
    if (numsSize == 0)
        return 0;

    //定义dp数组
    int dp[2505];//明确dp数组的含义：dp[i]表示以i为下标的最长递增子序列的长度为dp[i]
    int i, j;

    //初始化：为什么设置为1？因为一个元素的最长递增子序列最短也为本身，依次为1
    for (i = 0; i < numsSize; i++)
    {
        dp[i] = 1;
    }
    
    int maxn = 1;
    for (i = 1; i < numsSize; i++)
    {
        for (j = 0; j < i; j++)
        {
            if (nums[j] < nums[i])/*条件很重要*/
            {
                dp[i] = dp[j] + 1;
            }
            
            if (dp[i] > maxn)
                maxn = dp[i];
        }
    }

    return maxn;
}

C++代码：

class Solution {//Solution：类名
public://公有，外部也可使用共有的函数
//private：私有，外部不可使用共有的函数
//protect：私有，外部不可使用共有的函数
    int lengthOfLIS(vector<int>& nums) 
    {
        if (nums.size() == 0)
            return 0;
        
        vector<int>dp(nums.size(), 1);//可理解未一维数组
        //dp这个数组nums.size()这么大的空间的元素都赋值为1
    

        int i, j;
        int maxn = 1;
        for (i = 0; i < nums.size(); i++)
        {//nums.size()直接求出数组长度
        //不需要你像c语言一样：size = sizeof(dp) / sizeof(dp[0])
            for (j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
            if (dp[i] > maxn)
                maxn = dp[i];
        }
        return maxn;
    }
};