抚州网站开发机构,云南建设厅网站职称评定,外贸网站建设哪家合适,自己做的网站怎么放视频教程是我在学习动态规划时遇到的一道题。
题目#xff1a; 一共有两种解法#xff1a;
动态规划贪心 二分#xff08;很难理解#xff0c;我还没完全懂。。。#xff09; 解法一#xff1a;动态规划
思路#xff1a;
状态#xff1a;nums的前i个数的最长递增子序列。dp…是我在学习动态规划时遇到的一道题。
题目 一共有两种解法
动态规划贪心 二分很难理解我还没完全懂。。。 解法一动态规划
思路
状态nums的前i个数的最长递增子序列。dp[i]
转移方程依次计算每个状态dp[i]的状态这个状态依赖于前dp[0...i-1]的状态。
如果大于前面的数nums[j] nums[i]则说明有递增现象了。起码nums[j] nums[i]是一对的如果j前面还有子序列那岂不是美哉总之dp[i] dp[j] 1。但是别急万一这个dp[j]小赋值了反而dp[i]就变小了。我们要的是最长的先要比较再确定。
主要是为了防止这种情况【3 4 5 6 0 1 2 7】
比如这个时候7已经和6比完了76所以dp[7]dp[3]1
然后又和0比70如果直接dp[7]dp[4]1那么dp[7]就会变成2了。 最后找到dp里最大的就是我们想要的。
复杂度计算
时间复杂度O(n^2) 空间复杂度O(n)
代码
#include vector
//最长递增子序列
//解法一动态规划
//时间复杂度O(n^2)
//空间复杂度O(n)
class Solution {
public:int lengthOfLIS(std::vectorint nums) {//状态就是前i个数最长递增子序列std::vectorint dp(nums.size(), 1);//状态int max_count 1;for (int i 1; i nums.size(); i)//一个一个状态算{//转移方程for (int j 0; j i ; j)//查询前面的数是否小于{if (nums[j] nums[i])//如果大于前面的数则说明有递增{dp[i]std::max(dp[i], dp[j] 1);//有递增也不能直接赋值有可能这个dp[j]小赋值了反而dp[i]就变小了}}max_count max_count dp[i] ? max_count : dp[i];//取最大的dp[i]}return max_count;}
};void Test_solution1()
{std::vectorint nums{ 1,3,6,7,9,4,10,5,6 };Solution solution;std::coutsolution.lengthOfLIS(nums);
} 解法二贪心 二分
思路
二分就是用来查找的。关键是用贪心创建的dp[]是一个单调递增的所以可以二分查找。
很难解释因为我也一知半解。挖个坑
复杂度计算
时间复杂度O(nlogn) 空间复杂度O(n)
代码
#include vector
//最长递增子序列
//解法二贪心 二分
//时间复杂度O(nlogn)
//空间复杂度O(n)
class Solution {
public:int lengthOfLIS(std::vectorint nums) {//dp[x]:长度为x的最长递增子序列的最小一个末尾值//举个例子{1,2,3,4,5,6} // 长度为3的最长递增子序列有好几个比如{1,2,3} {3,4,5} {4,5,6}他们有各种末尾值但是最小的一个末尾值是3std::vectorint dp(nums.size(),0);//dp实际有多长len就意味着最长递增子序列有多长dp[0] nums[0];int len 0;//初始化长度为1指着dp第一个数dp[0]for (int i 1; i nums.size(); i){if (nums[i] dp[len]){len;dp[len] nums[i];}else{int j 0, z len;while (j z){int mid (j z) / 2;if (dp[mid] nums[i])j mid 1;else z mid;}dp[j] nums[i];}}//for (const auto x : dp)//{// std::cout x ;//}//std::cout std::endl;return len 1;}
};void Test_solution2()
{//std::vectorint nums{ 1,3,6,7,9,4,10,5,6 };std::vectorint nums{ 5,6,7,8,9,1,2,3,4 };Solution solution;std::cout solution.lengthOfLIS(nums);
}
