300. 最长递增子序列（C++题解含VS可运行源程序）

300. 最长递增子序列（C++题解含VS可运行源程序）

300. 最长递增子序列（C++题解含VS可运行源程序）

• 1.题解
• • 动态规划
• 2.力扣C++源码
• 3.VS可运行源程序

1.题解 动态规划

• 首先要定义 dp 数组的含义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

eg:

index012345nums143423dp12232？

• 根据这个定义，我们的最终结果（子序列的最大长度）应该是 dp 数组中的最大值。

求状态转移方程：

• 根据刚才我们对 dp 数组的定义，现在想求 dp[5] 的值，也就是想求以 nums[5] 为结尾的最长递增子序列。
• nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3
  接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。
• 当然，可能形成很多种新的子序列，但是我们只要最长的，把最长子序列的长度作为 dp[5] 的值即可。
• 我们可以定义一个变量 j，它和变量 i 具有同样的意思 ( dp[ j ] 是以 nums[ j ] 这个元素结尾的最长升序子序列的长度)，其中 0 ≤ j < i ，当 num[i] > num[j] 时可以认为 dp[i] = dp[j] + 1(当前的子序列长度通过之前的子序列长度加 1 求得），然而 j 代表 i 之前的所有元素 且我们要取最优解也就是所有 dp[j]中最长的，则有状态转移方程 dp[i] = max(dp[j]) + 1 （满足递增序列需要的判断条件: nums[i] >nums[j] );
• 由于每个最长子序列的初始长度都是 1 也就是只有它本身，我们可以规定边界：dp[i] 的初始值为 1；
• 像这种最长，最优的问题一般都可以使用动态规划，大致可以理解为将要求的问题分解为一个一个子问题，通过求子问题的最优解来求原问题的最优解；

2.力扣C++源码

class Solution {
public:
	int lengthOfLIS(vector& nums) {
		int max_ = 0;// 最长子序列长度
		int dp[2500];  // dp(i) 是以 nums[i] 结尾的最长递增子序列的长度
		for (int i = 0; i < nums.size(); i++) {
			dp[i] = 1;   // 边界 每个子序列的初始值
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {  // 状态转移方程判断条件
					dp[i] = max(dp[i], dp[j] + 1); // dp[i] = max(dp[j]) + 1
				}
			}
			// 每次都取出最长递增子序列的长度
			max_ = max(dp[i], max_);
		}
		return max_;
		}
};

3.VS可运行源程序

#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma warning(disable:4996)
using namespace std;

const int N = 2500;
class Solution {
public:
	int lengthOfLIS(vector& nums) {
		int max_ = 0;// 最长子序列长度
		int dp[2500];  // dp(i) 是以 nums[i] 结尾的最长递增子序列的长度
		for (int i = 0; i < nums.size(); i++) {
			dp[i] = 1;   // 边界 每个子序列的初始值
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {  // 状态转移方程判断条件
					dp[i] = max(dp[i], dp[j] + 1); // dp[i] = max(dp[j]) + 1
				}
			}
			// 每次都取出最长递增子序列的长度
			max_ = max(dp[i], max_);
		}
		return max_;
		}
};
int main()
{
	printf("输入数组元素个数：");
	int n;
	scanf("%d", &n);
	printf("输入数组元素：");
	int num;
	vector nums;
	for (int i = 0; i < n; i++) {
		scanf("%d", &num);
		nums.push_back(num);
	}
	Solution test;
	int ans = test.lengthOfLIS(nums);
	printf("最长严格递增子序列的长度为：%d", ans);


	printf("n");
	system("pause");
	return 0;
}