昨天下午在Sicily上进行算法分析期中测试，遇到一道这样的题目：求最小和。
从数列A[0], A[1], A[2], ..., A[N-1]中选若干个数，要求对于每个i（0<=i<N-1），A[i]和A[i+1]至少选一个数，求能选出的最小和.
1 <= N <= 100000, 1 <= A[i] <= 1000
请为下面的Solution类实现解决上述问题的函数minSum，函数参数A是给出的数列，返回值为所求的最小和.
class Solution {
public:
int minSum(vector<int>& A) {
}
};
例1：A = {2, 5, 2}，答案为4.
例2：A = {2, 5, 4}，答案为5.
注意：你只需要提交Solution类的代码，你在本地可以编写main函数测试程序，但不需要提交main函数的代码. 注意不要修改类和函数的名称.
我的思路是这样的：一般情况下，对于每一个选定的数字，都会遇到这样的问题，接下来是要选取它右边第一个数还是第二个数呢？无论我们选择哪个，选后又会遇到同样的问题。其实这便是一个递归的思路，我的完整本地测试代码如下：
#include <iostream>
using namespace std;
#include <vector>int min(vector<int>& A, int x) {int s = A.size();int len = s - x;if (len = 1 || len == 2) return A[x];else {int r = min(A, x + 1)<min(A, x + 2)?min(A, x + 1):min(A, x + 2);return A[x] + r;}}int minSum(vector<int>& A) {int s = A.size();if (s == 0) return 0;if (s == 1) return A[0];elsereturn min(A, 0)<min(A, 1)?min(A, 0):min(A, 1);}int main() {int a[7] = {5,4,5,6,8,5,2};//自行修改各项例子vector<int> b(a,a+7);int sum = Solution::minSum(b);cout << sum << endl;return 0;
}
然而，在提交代码后，却得到了Time Limit Exceeded的反馈。递归算法确实时间复杂度太大。于是改成了动态规划的方案，如下：
class Solution {
public:int minSum(vector<int>& A) {int s = A.size();if (s == 0) return 0;if (s == 1) return A[0];int a[s], b[s];//a表示不选择第i个，b表示选择第i个 a[0] = 0;b[0] = A[0];for (int i = 1; i < s; i++) {a[i] = b[i-1];b[i] = min(a[i-1], b[i-1]) + A[i];}return min(a[s-1], b[s-1]);}
};成功提交。
于是本周leetcode也选择了动态规划的相关问题：LeetCode 70. Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
即：给定楼梯层数n，每一步只能走1层或者2层，问上到楼梯顶有多少种方式？
Note: Given n will be a positive integer.
Example 1:
Input: 2 Output: 2 Explanation: There are two ways to climb to the top.1. 1 step + 1 step 2. 2 steps
Example 2:
Input: 3 Output: 3 Explanation: There are three ways to climb to the top.1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step
由于每次只能走1步或2步，所以可以在（n-1）次的结果里，加上最后一次“跨1步”，也可以在（n-2）次的结果里，加上最后一次“跨2步”.递归思想如下：
class Solution {
public:int climbStairs(int n) {if(n <= 2) return n;return climbStairs(n-1) + climbStairs(n-2);}
};然而，依旧是超时了。改成动态规划，自底向上求解：
class Solution {
public:int climbStairs(int n) {if(n <= 2) return n;int step[n+1];step[1] = 1;step[2] = 2;for(int i = 3; i <= n; i++){step[i] = step[i-1] + step[i-2];}return step[n];}
};或者是将空间复杂度再次降低：
class Solution
{
public:int climbStairs(int n){int a = 0, b = 1, res = 0;for(int i = 0; i < n; ++ i){res = a + b;a = b;b = res;}return res;}};自我总结：递归与动态规划的思路区别----前者采取自上而下，而后者采取自底向上。