福州网站建设搭建,昆明装修公司,张店网站建设,wordpress评论微信通知目录
动态规划怎么学#xff1f;
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后#xff1a; 动态规划怎么学#xff1f;
学习一个算法没有捷径#xff0c;更何况是学习动态规划#xff0c;
跟我…目录
动态规划怎么学
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后 动态规划怎么学
学习一个算法没有捷径更何况是学习动态规划
跟我一起刷动态规划算法题一起学会动态规划
1. 题目解析
题目链接53. 最大子数组和 - 力扣LeetCode 题目很好理解顾名思义就是找最大的子数组和。
2. 算法原理
1. 状态表示
dp [ i ] 位置表示以 i 位置元素为结尾的所有子数组的最大和。
2. 状态转移方程
状态转移方程有两种情况
1. 子数组长度为 1 时最大和就是 i 位置的值
2. 子数组长度大于 1 是最大和就是上一个位置的最大和 当前位置的值
所以我们就可以得出状态转移方程
dp [ i ] max( nums[ i ]dp[ i ] nums[ i ] )
3. 初始化
初始化就是防止越界并且不影响后面的值
初始化成 0 即可。
4. 填表顺序
从左往右即可。
5. 返回值
返回整个 dp 表里的最大值。
3. 代码编写
class Solution {
public:int maxSubArray(vectorint nums) {int n nums.size();vectorint dp(n 1);int ans INT_MIN;for(int i 1; i n ; i) {dp[i] max(nums[i - 1], dp[i - 1] nums[i - 1]);ans max(ans, dp[i]);}return ans;}
};
写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
