昆山快速建设网站方案,网站模板模仿,江苏建设电子证书查询,wordpress.程序做目录
动态规划怎么学#xff1f;
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后#xff1a; 动态规划怎么学#xff1f;
学习一个算法没有捷径#xff0c;更何况是学习动态规划#xff0c;
跟我…目录
动态规划怎么学
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后 动态规划怎么学
学习一个算法没有捷径更何况是学习动态规划
跟我一起刷动态规划算法题一起学会动态规划
1. 题目解析
题目链接300. 最长递增子序列 - 力扣LeetCode 这道题目题如其名就是找出最长的递增子序列然后返回长度
但是我们需要明确的是什么是子序列什么是子数组一定要分清楚
子数组必须要连续的
而子序列不需要连续的我们可以通过示例一来感受
只要是在这个数组区间里的元素是递增的可以跳着选择
总结来讲就是子序列是可以在一个区间跳着选择的也就是可以使不连续的。
2. 算法原理
1. 状态表示
dp[ i ] 表示以 i 位置结尾的所有子序列中最长递增子序列的长度。
2. 状态转移方程
我们可以分成两种情况
第一种情况是 i 位置自己作为一个子序列那长度就是 1
第二种情况是 i 位置和前面任意一个位置构成子序列我们把大于等于 0 小于 i 的这个位置设为 j
因为题目要求的是递增所以需要 nums[ j ] nums[ i ]等于 dp[ j ] 1
而 j 有很多种情况所以就是求 0 j i - 1 位置 dp[ j ] 的最大值。
3. 初始化
我们可以把表初始化成 1 这样我们就可以只考虑第二种情况了。
4. 填表顺序
从左往右。
5. 返回值
返回 dp 表里的最大值即可。
3. 代码编写
class Solution {
public:int lengthOfLIS(vectorint nums) {int n nums.size();vectorint dp(n, 1);for(int i 1; i n; i) for(int j 0; j i; j) if(nums[j] nums[i]) dp[i] max(dp[j] 1, dp[i]);int ans INT_MIN;for(auto e : dp) ans max(ans, e);return ans;}
};写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
