知识点：LIS问题，动态规划分析：状态表示：1.f[i]表示以第i个数字结尾的子序列的最长的递减种子序列2.属性：max，最长状态计算：1.分为两个部分1.1一个部分是，包含seeds[i]这个数字的，那么以这个结尾的最长的递减子序列长度，抛开这个即将要计算的seeds[i]数字来说，其最长长度为f[j]+1，其中j取的是0~i，表示取一个最长的之前计算的最长递减长度，再加11.2另一个部分是不包含seeds[i]的，那么就是以上一个包含了seeds[i]的数字结尾的长度，也就是之前计算的f[i]综上，f[i] = max(f[i],f[j]+1)编程语言：C++完整代码： int f...

知识点：动态规划环形分析：环状排列意味着第一块草料和最后一块草料中只能选择一个吃，因此可以把此环状排列化为两个单排排列子问题在不吃第一块草料的情况下，最高饱腹感是p1；在不吃最后一块草料的情况下，最高饱腹感是p2。最高饱腹感： 为以上两种情况的较大值，即 max(p1,p2)。编程语言：C++完整代码： int f[1010]; int g[1010]; int eat(vector<int>& nums,int st,int ed,int* f) { if(nums.size() <= 1) return nums.size(...

知识点：动态规划分析：状态表示：1.f[i]表示吃第i块草的时候的最高饱腹感值。3.属性：max，最高/最大状态计算：f[i]两种情况：1.如果吃当前i块草的话，那么f[i] = f[i-2] + nums[i] 相邻的草不可以吃2.如果不吃当前草的话，那么f[i]= f[i-1]所以f[i] = max(f[i-2] + nums[i], f[i]= f[i-1])编程语言：C++完整代码： int eatGrass(vector<int>& nums) { if (nums.size() == 0) return 0; if (...

知识点：动态规划分析:会了牛群的能量，也就会这个了。 变换就是变为了环形数组分两种情况。 (1)答案在数组中间，就是最大子序和。例如[1,-2,3,-2]； (2)答案在数组两边，例如[5,-3,5]最大的子序和就等于数组的总和SUM - 最小的子序和。(一种特殊情况是数组全为负数，也就是SUM-最小子序和==0，最大子序和等于数组中最大的那个)。编程语言：C++完整代码： int maxEnergyCircular(vector<int>& energy) { int total = 0, curMax = 0, maxSum = energy[0], c...

知识点数组的最大子数组和贪心算法分析从这群牛中选择一个连续的子群，使得这个子群的能量值之和最大。连续的子群的话，那么就可以去依次遍历这个能量数组，当能量和小于0的时候必定不是一个能量值之和最大的子数组，那么就需要将累计的和置为0，再从下一个能量继续积累。直到数组遍历结束编程语言C++完整代码 int maxEnergy(vector<int>& energy) { int sum = 0; int res = -1e9; for(int i = 0;i<energy.size();i++){ ...

知识点动态规划分析 如果N=1，共有1种方案； 如果N=2，共有2种方案； 如果N=3，可以吃1，剩2，也可以吃2，剩下1，所以共有2+1=3种方案； 如果N=4，则吃1，剩3，也可以吃2，剩2，共有3+2=5种方案。 则f[i] = f[i - 1] + f[i - 2]那么使用动态规划就可以解决了。编程语言C++完整代码 int eatGrass(int n) { int f[10010] = {0}; f[1] = 1; f[2] = 2; for (int i = 3; i <= n; i++){ f[i] ...