Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。
🌈个人主页：主页链接
🌈算法专栏：专栏链接
我会一直往里填充内容哒！
🌈LeetCode专栏：专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出
🌈代码仓库：Gitee链接
🌈点击关注=收获更多优质内容🌈
介绍了动态规划相关的题目与题解.
题目:最长上升子序列
题解:
首先进行分析，这题的状态是什么？
状态为:前i个上升子序列的长度.
属性为:max(因为题目为最长)
所以令dp[i]初始化为1(本身也是一个长度)
之后循环遍历前i个字符,若发现其满足a[j]<a[i] 则更新子序列
状态方程为:dp[i]=max(dp[i],dp[j]+1]
代码实现:
#include<iostream> #include<algorithm> using namespace std; const int N=1010; int a[N]; int f[N]; int main() { int n=0; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=n;i++) { f[i]=1; for(int j=1;j<i;j++) { if(a[i]>a[j])f[i]=max(f[j]+1,f[i]); } } int res=-1e9-100; for(int i=1;i<=n;i++)res=max(res,f[i]); cout<<res; }
题目:最大子数组和
题解:
拿到题目也首先分析,这题的状态是什么?
找出一个具有最大和的连续数组,细看一下和上面那题十分的像.但这题要求得是连续的子数组
这题似乎也能用滑动窗口来做?
是不能的,因为有负数滑动窗口作左区间的无法判断何时进行缩进.
所以这里的状态为前i个数字中相加子数组的最大值.
也就是每一个dp[i]存储的都是之前的最优解
所以我们要考虑的就是 当前第i位的数字,是用他本身,还是加上之前的dp[i-1]后再加它本身.(本身是一定要加的,不然就不连续了).这就是我们的属性
所以状态方程为 dp[i]=max(nums[i],dp[i-1]+nums[i])
例如:
代码实现:
#include <algorithm> #include<iostream> #include<vector> using namespace std; class Solution { public: int maxSubArray(vector<int>& nums) { vector<int>ans(nums.size()+1); if(nums.size()==0)return 0; ans[1]=nums[0]; for(int i=1;i<ans.size();i++) { ans[i]=nums[i-1]; ans[i]=max(ans[i],ans[i-1]+nums[i-1]); } int t=-1e5; for(int i=1;i<ans.size();i++) { if(ans[i]>t)t=ans[i]; } return t; } };
完结撒花：
🌈本篇博客的内容【动态规划:最长上升子序列、最大子数组和题解及代码实现】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！
