锐客网

  1. 首页 > 睿知 > it技术 > >

leetcode|动态规划-爬楼梯，连续子数组的最大和

leetcode

1.以爬楼梯问题为例，总结动态规划的步骤：
第一步：定义dp数组（可能时一维数组，也可能是二维数组），这一步需要确定两个问题：
（1）dp[i]或者dp[i][j]是什么含义（比如在爬楼梯问题中，dp[i]表示到达第i层有多少种爬法）
（2）到底开多大的空间，你搞懂了第一个问题dp[i]或者dp[i][j]是什么含义，就知道到底要开多大的空间了，由于在爬楼梯问题中，dp[i]表示到达第i层有多少种爬法，你最后求的是到达第n层所需要的爬法数，所以最后要返回的是dp[n]，所以显然要开n+1大小的数组，这样才能有dp[n](如果你只开n大小的数组，那么最后只能返回dp[n-1]
第二步：初始化这个数组中的部分值
【leetcode|动态规划-爬楼梯，连续子数组的最大和】dp[0]题目已经给了等于1
dp[1]就是到达第一层有几种爬法，显然dp[1]=1
第三步：/写出状态转移方程确定dp数组中其他位置元素的值

爬楼梯问题：爬到第n层有可能是从第n-1层然后跨一层到达第n层的，也可能时从第n-2层然后跨两层到达第n层的
青蛙跳台阶：力扣

class Solution { public int numWays(int n) { if (n == 0) return 1; if (n == 1) return 1; //定义一个dp数组，dp[i]表示到达第i层有多少种爬法 int[] dp = new int[n + 1]; //初始化dp数组 dp[0] = 1; dp[1] = 1; //写出状态转移方程确定数组中其他位置元素的值 for (int i = 2; i <= n; i++) { dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007; } return dp[n]; } }

爬楼梯：力扣
class Solution { public int climbStairs(int n) { if(n==1)return 1; if(n==2)return 2; ArrayList result=new ArrayList(); result.add(0); result.add(1); result.add(2); for(int i=3; i<=n; i++) { result.add(result.get(i-1)+result.get(i-2)); } return result.get(n); } }

2.连续子数组的最大和力扣53
比如数组为nums[]:1，-2，3，10，-4，7，2，-5
以1结尾的所有子数组，以-2结尾的所有子数组，以3结尾的所有子数组.........以7结尾的所有子数组，以2结尾的所有子数组，以-5结尾的所有子数组
开一个数组dp[nums.length],
dp[i]表示以nums[i]结尾的所有子数组中最大和
比如：dp[0]表示以nums[0](也就是1）结尾的所有子数组中最大和，显然dp[0]=1
dp[1]表示以nums[1]（也就是-2）结尾的所有子数组中最大和，显然dp[0]=1
.......
显然dp[i+1]=max(nums[i+1],dp[i]+nums[i+1])
也就是说，dp[i+1]要么就是等于dp[i]加上nums[i+1]，要么就是不要前面的子序列，只要nums[i+1]这个数
class Solution { public int maxSubArray(int[] nums) { int[] dp=new int[nums.length]; dp[0]=nums[0]; for(int i=0; i


    推荐阅读


    上一篇：leetcode|a=a*10+b型题目

    下一篇：leetcode|leetcode 滑动窗口