303. Range Sum Query - Immutable
解题思路：
Note里说sumRange会被调用很多次。。所以简直强烈暗示要做cache啊。。。所以刚开始，虽然用每次都去遍历数组求和的方式可以
AC，但是真的耗时太长了。因此，考虑不存储数组nums，而是在array[i+1]处存前i项的和。这样的话，求i和j之间的和，只需要用
array[j+1]-array[i]即可以求得了。这样是直接访问数组，会快很多。
class NumArray {
public:
NumArray(vector<int> nums) {
// default is 0
array = new int[nums.length() + 1];
for (int i = 0; i < nums.length(); i++) {
array[i + 1] = array[i] + nums[i];
}
}
int sumRange(int i, int j) {
return array[j + 1] - array[i];
}
private:
// Notice
int[] array;
};
70. Climbing Stairs
解题思路：
类似汉诺塔问题。。
int climbStairs(int n) {
if (n <= 2)
return n;
// from n-1 to n
int oneBefore = 2;
int twoBefore = 1;
int sum = 0;
for (int i = 2; i < n; i++) {
sum = oneBefore + twoBefore;
twoBefore = oneBefore;
oneBefore = sum;
}
return sum;
}
198. House Robber
解题思路：
由题目可知，不能抢劫相邻的两家，所以可以考虑单数线和双数线。
int Max(int a, int b) {
return a > b ? a : b;
}
int rob(vector<int>& nums) {
int even = 0;
int odd = 0;
for(int i = 0; i < nums.size(); i++) {
if (i % 2 == 0)
// if odd is bigger, nums[i-1] is chosen and nums[i] isn‘t chosen
// otherwise, nums[i] is chosen.
even = Max(even + nums[i], odd);
else
odd = Max(even, odd + nums[i]);
}
// return max of two lines
return Max(even, odd);
}
leetcode-20-Dynamic Programming
原文：http://www.cnblogs.com/pxy7896/p/6684010.html