很多面试笔试题目涉及到的大部分都是DP的题目,这部分试题灵活性较高,而其中最重要的就是找出状态转移方程,方程找的好相当于成功了一半。
这类题目需要不断地刷题来总结套路,总结就是多做题多总结多分析。
[0] 定义特殊情况。
这部分的主要任务就是把特殊情况先列明解决掉,比如数组为null时候,直接return .....
【这一步有时候题目没有特殊情况的时候是可以省略的】
[1] 定义dp数组
这一步是定义dp数组,而dp数组的含义一般为题目所求的问题
即你想求什么问题,就定义dp数组的含义是什么
[2] 找出状态转移方程
真正的大头就是 == 状态转移方程 == 的查找了。
一般是将题目所求的大问题分解成小问题去寻找之间的关系。
题目要求dp[n],我们可以向高中数学一样,列出dp[n-1],dp[n-2].........观察他们之间的关系。
一般这里都会用到for循环
tips:我自己做题的一个技巧
前期不熟悉的时候很难观察出各项之间的关系,可以举例子,每一项都计算出具体的数字,观察每一项之间的关系
这个对于新手的帮助是挺大的。
【注意的一点是】状态转移方程一定要体现出前后几项之间的关系
[3] base case
这一步就是初始条件的定义,比如dp[0]是什么,dp[1]是什么,定义几个初始条件
具体定义情况视题目而定。
以上即为做动态规划题目的几个套路,按部就班来做一般思路都会有的,剩下的就是多做题多总结了。
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
提示:
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
下面就是根据上面总结的四步法进行这道题目的分析以及求解。
【0】 特殊情况的讨论 。
这道题由于【1 <= arr.length <= 10^5】的限制,即数组不为null,所以这一步可以省略。
【1】 定义dp数组。
题目所求为连续子数组的最大和,则定义一个dp数组,长度和原数组一样,每个位置的元素的意义是以当前元素为结尾的子数组的最大和,即dp[ ]数组存储 的是每个元素的子数组的最大和,那么最终结果就是遍历dp数组返回它的max值即可。
[tips]:注意这里的子数组包括元素本身,即元素本身也可作为一个子数组,这个情况是我做题没考虑的,提交leetcode的时候才发现有点bug。要把这种情况也加进去比较讨论
【2】状态转移方程的确立。
状态转移方程要体现前后者的关系,以n结尾的子数组的和等于以n-1结尾的子数组的最大和与第n-1个元素对比后的Max 加上本身第n个元素,
即dp[n] = Math.max(dp[n-1],nums[n-1]) +nums[n]
【3】 base case
dp[0]=nums[0].即dp数组最开始的元素为nums数组第0个元素,就是本身。
代码如下,代码上面也加了注解,方便阅读。
【如果题目要求书写ACM模式,可以看我下一篇文章】
tips:ACM模式解法
class Solution {
public int maxSubArray(int[] nums) {
int n=nums.length;
//1.定义dp数组
int[] dp=new int[n];
//3.base case
dp[0]=nums[0];
//2.状态转移方程
for(int i=1;i<n;i++){
//可以通过具体的数字列明观察各个数之间的关系
//得出状态转移方程,这个状态转移方程一定要能够体现出来i项和i-1项之间的区别。
dp[i]=Math.max( (Math.max(dp[i-1],nums[i-1]) +nums[i]), nums[i] );
//这里还要再添加和它本身的一个对比,比如[-2,1],最大子序列和为它本身即1.
}
//遍历dp数组找出max元素
int max=dp[0];
for(int i=1;i<n;i++){
if(dp[i]>max){
max=dp[i];
}
}
return max;
}
}
Epoll 是个很老的知识点,是后端工程师的经典必修课。这种知识具备的特点就是研...
详解Spring mvc ant path的使用方法 概要: 任何一个WEB都需要解决URL与请求处理...
戳蓝字“ CSDN云计算 ”关注我们哦 作者 | 刘丹 出品 | CSDN云计算IDCSDNcloud ...
堆 Heap Heap:可以迅速找到一堆数中的 最大 或者 最小 值的数据结构。 将根节点...
这里尊托云数小编参考了几篇文章特为大家整理下,用到的朋友多支持一下了。 进行...
WebService端代码 复制代码 代码如下: /// summary /// 上传文件到远程服务器 //...
1.现在复习的感觉就是:马上要有一大波僵尸涌过来,但老子连向日葵都还没种! 2...
IViewLocationExpander API ExpandViewLocations Razor视图路径,视图引擎会搜索...
项目背景 最近项目里有个webpack版本较老的项目,由于升级和换框架暂时不被leade...
20210323第一家量产国产化蓝牙AOA高精度定位基站生态合能培训会上海站现场直播下...