【Day28 LeetCode】动态规划DP
一、动态规划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方程确定遍历顺序。