【LeetCode】动态规划篇

• 撸码时间
• • 1、爬楼梯
  • 2、最大子数组和

题目描述：需要爬n阶才能到达楼顶。每次可以爬1或2个台阶。请问有多少种不同的方法可以爬到楼顶？（1<=n<=45）
解法1
思路：假设已经到达了楼顶，现在往后退一步，由于一次只能爬1或2个台阶，那么退一步就是在n-1或n-2的位置，假设到达n-1个台阶时有i种走法，n-2有j中走法，那么最终到达n处就是i+j种走法。再分别从n-1处和n-2处各退一步，以此类推…临界点为n=1和n=2时走法各为1和2。
代码如下：

public int climbStairs(int n) {
   if (n == 1){
     return 1;
   }
   if (n == 2){
     return 2;
   }
   return climbStairs(n-1)+climbStairs(n-2);
}

代码运行结果是正确的。但是在LeetCode上提交时，n=45的时候超时…
于是就使用了解法2
解法2：菲波那切数列
思路：n=1时sum=1，n=2时sum=2；n=3时sum=3；n=4时sum=5；n=5时sum=8…由此可以发现这是一个菲波那切数列，即，后面一项等于前两项之和。
代码：

public int climbStairs(int n) {
	 int pre = 1;
	 int next = 1;
	 int num = 1;
	 for (int i = 2; i <= n; i++) {
	     num = pre + next;
	     pre = next;
	     next = num;
	 }
	 return num;
}

过辣~

题目描述：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
（子数组 是数组中的一个连续部分。）

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6

输入：nums = [-1]
输出：-1

输入：nums = [5,4,-1,7,8]
输出：23

解法1：一力降十会
思路：其实第一眼看到这道题，脑子有点乱…先暴力解试试看。首先依次从数组的每个数开始遍历，每个数遍历时依次往后加。

public int maxSubArray(int[] nums) {
    int max = nums[0];
    for (int i = 0; i < nums.length; i++) {
        int temp = nums[i];
        if (temp > max){
            max = temp;
        }
        for (int j = i+1; j < nums.length; j++) {
            temp += nums[j];
            if (temp > max){
                max = temp;
            }
        }
    }
    return max;
}

很明显，时间复杂度为O(n²)，所以…超时了呜呜呜呜！
不过这段代码应该没毛病~

解法2
看的一位大佬的解法。
思路：sum为子数组的和。假设现在sum是前n-1项的和，如果sum<=0，那么对第n项是没有帮助的，此时最大子数组和只能从第n项开始算起。只有sum>0时才会对第n项有帮助。所以当sum>0时，子数组和算上第n项。
每次保存一下sum的最大值即可。

public int maxSubArray(int[] nums) {
    int max = nums[0];
    int sum = 0;
    for (int num : nums) {
        if (sum>0){
            sum += num;
        }else{
            sum = num;
        }
        max = Math.max(sum,max);
    }
    return max;
}

过辣~