前言
「在线处理算法」解决LeetCode53.最大子序和
「动态规划」解决LeetCode70.爬楼梯
LeetCode53.最大子序和
问题描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例
|| 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
|| 输出：6
|| 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
解题思路
对于待求数组 nums ，我们将每一项向右累加，发现更大的当前子序和则更新最大子序和maxSum，如果当前子序和为负，它一定会使后面的数字变得更小，干脆抛弃，将当前子序和置为0，最后得到的结果即为最大子序和。
时间复杂度O(n)。
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len = nums.size();
int maxSum = nums[0]; //将最大子序和初始值设置为数组第一个数
int thisSum = 0; //当前子序和
for(int i=0;i<len;++i){
thisSum += nums[i];
if(thisSum>maxSum){
maxSum = thisSum; //发现更大的和则更新当前结果
}
if(thisSum<0){
thisSum = 0; //如果当前子序和为负.它一定会使后面的数变得更小,干脆抛弃,置和为0
}
}
return maxSum;
}
};
LeetCode70.爬楼梯
问题描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例
|| 输入：3
|| 输出：3
|| 解释：有三种方法可以爬到楼顶。
|| ① 1 阶 + 1 阶 + 1 阶
|| ② 1 阶 + 2 阶
|| ③ 2 阶 + 1 阶
解题思路
确定「状态定义」和「状态转移方程」
动态规划
为了与台阶数对应好理解，我们申请一个大小为 n+1 的数组 dp，
定义 dp[i] 为爬到第 i 个台阶的方法数，i>0
那么 dp[n] 为爬到第 n 个台阶的方法数，
dp[1]=1 和 dp[2]=2 为两个初始状态，我们每次可以爬 1 或 2 个台阶，
那么我们达到第 i 个台阶的方法数就等于到达第 i-1 个台阶的方法数加上到达第 i-2 个台阶的方法数，可得状态转移方程：dp[i] = dp[i-1] + dp[i-2];
代码
class Solution {
public:
int climbStairs(int n) {
if(n==1) //题目中规定n为正整数，不考虑小于1的情况
return 1;
int dp[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];
}
};