一、动态规划DP
动态规划中每一个状态一定是由上一个状态推导出来的，所以关键是确定状态转移方程。一般dp问题需要明确一下几点：dp数组及下标的含义、状态转移方程（dp方程）、dp数组初始化、根据dp方程确定遍历顺序。
1、斐波那契数 509
简单，斐波那契数列的表达式就是dp方程。
class Solution {
public:int fib(int n) {if(n <= 1)return n;int pre = 0, cur = 1;while(--n){int tmp = cur;cur += pre;pre = tmp;}return cur;}
};
2、爬楼梯 70
与上一题斐波那契数列类似，不过这题初始化条件不一样。
class Solution {
public:int climbStairs(int n) {int pre = 1, cur = 1;for(int i=2; i<=n; ++i){int tmp = cur;cur += pre;pre = tmp;}return cur;}
};
3、使用最小花费爬楼梯 746
这题与爬楼梯相似，dp方程dp[i]表示到达当前第i个台阶所需的花费，dp方程为dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])。初始化为dp[0]=dp[1]=0,因为可以从第0个或者第1个台阶出发。明确了初始化和转移方程，解决这类问题就很简单。
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n+1, 0); // dp数组for(int i=2; i<=n; ++i){dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);}return dp[n];}
};
空间优化版本如下：
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int pre = 0, cur = 0;for(int i=2; i<=cost.size(); ++i){int tmp = cur;cur = min(cur + cost[i-1], pre + cost[i-2]);pre = tmp;}return cur;}
};
二、写在后面
今天是dp简单的题目，主要是用来明确上面提到的那几点：dp数组及下标的含义、状态转移方程（dp方程）、dp数组初始化、根据dp方程确定遍历顺序。
