感觉就分几种类型：
第1种：连续求和类型（只用dp[i-1]）
题目：53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
代码：
class Solution {
public int maxSubArray(int[] nums) {
int ans=nums[0];
int dp=0;
for(int num:nums){
dp=Math.max(dp+num,num);
ans=Math.max(ans,dp);
}
return ans;
}
}
状态转换：
用记事本记下以该位置为结尾的最大子序列和，然后比较选出最大子序列和
与此相同的题目有
题目：面试题42. 连续子数组的最大和
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为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
第2种：斐波那契数列类型 （只用dp[i-1]和dp[i-2]）
题目 70. 爬楼梯
70.爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
代码：
class Solution {
public int climbStairs(int n) {
if(n==1)return 1;
if(n==2)return 2;
int[] dp=new int[n+1];
dp[1]=1;
dp[2]=2;
for(int i = 3 ; i <= n ; i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
}
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:
输入：n = 3
输出：4
说明: 有四种走法
示例2:输入：n = 5
输出：13
提示:n范围在[1, 1000000]之间
代码：
class Solution {
public int waysToStep(int n) {
int[] dp=new int[n+1];
switch(n){
case 1:return 1;
case 2:return 2;
case 3:return 4;
}
dp[1]=1;
dp[2]=2;
dp[3]=4;
for(int i = 4; i< n+1;i++){
dp[i]=((dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007;
}
return dp[n];
}
}
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
示例 1：
输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
示例 2：输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
示例 3：输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
代码：
class Solution {
public int massage(int[] nums) {
if(nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
int[] dp= new int[3];
dp[0]=nums[0];
dp[1]=Math.max(nums[0],nums[1]);
for(int i = 2; i < nums.length; i++){
dp[i%3]=Math.max(dp[(i-2)%3]+nums[i],dp[(i-1)%3]);
}
return dp[(nums.length-1)%3];
}
}
利用取余降低空间复杂度。
题目：198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
代码：
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if(len==0)return 0;
if(len==1)return nums[0];
int[] dp=new int[3];
dp[0]=nums[0];
dp[1]=Math.max(nums[0],nums[1]);
for(int i = 2; i <len; i++){
dp[i%3]=Math.max(dp[(i-1)%3],dp[(i-2)%3]+nums[i]);
}
return dp[(len-1)%3];
}
}
数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
示例 2:输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
注意：cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。
代码：
class Solution {
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int[] dp = new int[len];
dp[0]=0;
dp[1]=Math.min(cost[0],cost[1]);
for(int i = 2; i < len; i++){
dp[i]=Math.min(dp[i-1]+cost[i],dp[i-2]+cost[i-1]);
}
return dp[len-1];
}
}
总结：只是利用本子把前两个数记下来
第3种简单状态转换公式（用一维数组dp[N+1]记录前后之间关系）
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
示例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:你可以假设数组不可变。
会多次调用 sumRange 方法。
代码：
class NumArray {
int[] nums=null;
int sum=0;
int[] dp=null;
public NumArray(int[] nums) {
this.nums=nums;
int[] dp=new int[nums.length+1];
dp[0]=0;
for(int i = 1 ; i< nums.length+1;i++){
sum+=nums[i-1];
dp[i]=sum;
}
this.dp=dp;
}
public int sumRange(int i, int j) {
return (dp[j+1]-dp[i]);
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
记事本简单记的是true或false（Y or N)
根据上一步的结果来判断下一步操作。
题目：1025. 除数博弈
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
示例 1：
输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
示例 2：输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。提示：
1 <= N <= 1000
代码：
class Solution {
public boolean divisorGame(int N) {
if(N==1)return false;
int[] dp=new int[N+1];
dp[1]=0;
dp[2]=1;
for(int i = 3; i <N+1;i++){
for(int j = 1; j<i; j++){
if(i%j==0&&dp[i-j]==0){
dp[i]=1;
break;
}
}
}
return dp[N]==1;
}
}
外循环是记事本，内循环是过往的记事本，只要翻旧账能翻出符合条件的就把今天的事情翻篇。
第四种类型 两个对象比较 （用二维数组dp[M+1][N+1]表示之间的关系）
题目：392. 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1:
s = "abc", t = "ahbgdc"返回 true.
示例 2:
s = "axc", t = "ahbgdc"返回 false.
后续挑战 :
如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
代码：
class Solution {
public boolean isSubsequence(String s, String t) {
int slen=s.length();
int tlen=t.length();
int[][] dp=new int[slen+1][tlen+1];
if(slen==0){
return true;
}
if(tlen==0){
return false;
}
for(int i = 0; i <tlen; i++){
dp[0][i]=1;
}
for(int i = 1 ; i <=slen; i++){
for(int j = 1 ; j <=tlen; j++){
if(s.charAt(i-1)==t.charAt(j-1)){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=dp[i][j-1];
}
}
}
return dp[slen][tlen]==1;
}
}
当char[i]==char[j]时，则字符i一定是j的子序列，如果0 ~ i - 1 子字符串是0 ~ j - 1子字符串的子序列，则dp[i][j]=true，所以dp[i][j] = dp[i-1][j-1]；承接上一个状态；
当char[i]!=char[i]时，即判断当前0i子字符串是否是0j-1的子字符串的子序列，dp[i][j]=dp[i][j-1]; 承接上一个状态
网友评论