动态规划做题思路。
关键点：
1.dp[i][j]理解dp数据和i和j的含义
2.递归公式
3.dp初始化
4.遍历顺序
5.打印dp数组
https://leetcode.cn/problems/fibonacci-number/
dp数组含义：
dp[i] 表示第一个斐波拉契数是什么
递推公式：
dp[i] = dp[i-1] + dp[i-2]
初始化：
dp[0]=0;
dp[1] = 1
class Solution {
public:
int fib(int n) {
vector<int> dp(n+1,0);
dp[0] = 0;
if(n == 0)
return dp[0];
dp[1] = 1;
if(n == 1)
return dp[1];
for(int i=2;i<=n;i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
};
https://leetcode.cn/problems/climbing-stairs/
dp数组含义：
dp[i]表示爬到第i阶有多少种方法
递推公式：
dp[n] = dp[n-1] + dp[n-2]
表示最后一步如果是1级有dp[n-1]种方法
如果是2级，有dp[n-2]种方法。
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n+1, 0);
dp[0] = 0;
if(n==0)
return 0;
dp[1] = 1;
if(n==1)
return 1;
dp[2] = 2;
if(n==2)
return 2;
for(int i = 3;i<=n;i++)
{
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
https://leetcode.cn/problems/min-cost-climbing-stairs/
算法思想：
dp[i]表示爬到i个楼梯的最小花费
递推公式：
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2]+cost[i-2])
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n+1, 0);
dp[0]=0;
if(n==0)
return 0;
dp[1] = 0;
if(n==1)
return 0;
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];
}
};
