70 爬楼梯
比较简单的动态规划题，爬到第n阶的方法分为两类，要么是从n-1阶跨1步上来，要么是从n-2阶跨2步上来。用O(n)表示爬到n的方法，递推公式：
O(n) = O(n-1) + O(n-2)
O(1) = 1, O(2) = 2
代码：
class Solution {
public:
int climbStairs(int n) {
vector<int> O;
O.push_back(0);
O.push_back(1);
O.push_back(2);
for(int i = 3; i <= n; i++)
O.push_back(O[i-1] + O[i-2]);
return O[n];
}
};
121 买卖股票的最佳时机
这个题之前做过一个可以多次买卖的版本（买卖股票的最佳时机II），那个当时还是想了挺久的。今天这个只能买卖一次的，开始想复杂了，差点写个O(n^2)的出来，后来才想到应该怎么做。这个题目上耽误的时间有点多，还是不熟练啊。
其实很简单，只要能得到当前位置前的最小元素，就可以得到如果在当前位置卖出，能获取的最大利润。所以设置两个全局变量，一个是到当前位置为止的能获取的最大利润，一个是到当前位置位置前的最小元素，只要扫描一遍数组，同步更新这两个值就可以，甚至都不用递推方程和数组来存储结果。
这种做法的时间复杂度O(n)，空间复杂度O(1)，而且代码看起来也很简洁，我觉得还行。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1) return 0;
int max_profit = 0, cur_min = prices[0];
for(int i = 1; i < prices.size(); i++){
if(prices[i] - cur_min > max_profit)
max_profit = prices[i] - cur_min;
if(prices[i] < cur_min)
cur_min = prices[i];
}
return max_profit;
}
};
53 最大子序和
还是典型的动态规划题目，大二上算法课的时候第二个例题就是它。
用dp(i)表示以第i个元素结尾且包含第i个元素的最大子序和，递推公式：
dp(i) = max{num[i], dp(i-1) + num[i]}, i > 0
dp(0) = num[0]
最后扫描一遍dp数组，找出最大值就可以。还是O(n)的时间复杂度。
代码：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> O;
if(nums.size() == 0) return 0;
O.push_back(nums[0]);
for(int i = 1; i < nums.size(); i++){
int tmp = nums[i] > O[i-1] + nums[i] ? nums[i] : O[i-1] + nums[i];
O.push_back(tmp);
}
int max = O[0];
for(int i = 1; i < nums.size(); i++){
if(O[i] > max) max = O[i];
}
return max;
}
};
后来想了一下，这个题目是满足贪心的性质的，对于这种当前步计算结果只依赖于前一步计算结果的最优化问题，其实dp数组也可以不要，设置一个变量保存前一步结果，一个变量保存当前最优结果就可以了。这样只需要扫描一遍数组，并且空间复杂度是O(1)，代码也变得更加简洁了，非常棒棒。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int cur_max = nums[0], last_max = nums[0];
if(nums.size() == 0) return 0;
for(int i = 1; i < nums.size(); i++){
last_max = nums[i] > last_max + nums[i] ? nums[i] : last_max + nums[i];
cur_max = last_max > cur_max ? last_max : cur_max;
}
return cur_max;
}
};
题目还说能不能用更精妙的分治法来解，我觉得一点都不精妙好不好，解起来很麻烦，而且时间复杂度也没有变好，这种问题复杂度下界就是O(n)了，所以我就不尝试了，以后有时间再说吧。
198 打家劫舍
开始以为是个背包问题，后来发现没有背包，就是个普通的贪心问题，只不过当前的最优结果取决于前两步的最优结果，要多保存个变量。
当前的抢劫结果，就是抢或者不抢两种情况，抢的话，就是dp[i-2]+num[i], 不抢的话，就是dp[i-1]。两个里面取最大。
递推公式：
dp[i] = max{dp[i-1], dp[i-2]+num[i]}
代码：
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
int last_1 = nums[0], last_2 = nums[1] > last_1 ? nums[1] : last_1;
for(int i = 2; i < nums.size(); i++){
int tmp = last_2 > nums[i] + last_1 ? last_2 : nums[i] + last_1;
last_1 = last_2;
last_2 = tmp;
}
int max_pro = last_1 > last_2 ? last_1 : last_2;
return max_pro;
}
};
