动规五部曲:
——确定dp[i]含义
递推公式
dp数组如何初始化
遍历顺序
打印dp数组
dp[i]:第i个的斐波拉契数
递推公式:等于dp[i-2]+dp[i-1]
dp数组的初始化:dp[0] = 0,dp[1]=1
遍历顺序:从前向后
int fib(int n){
if(n <= 1){
return n;
}
int* dp = (int*)malloc(sizeof(int)*(n + 1));
dp[0] = 0;
dp[1] = 1;
int i;
for(i = 2; i <= n; ++i){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
dp[i]到达第i阶有dp[i]种方法
递推公式:dp[i-2]+dp[i-1]——因为有两种方法可以上楼梯,所以第上第i阶时应该是走到第i-2阶的方法加上第i-1阶的方法
dp数组的初始化:dp[0] = 0,dp[1]=1
遍历顺序:从前向后
int climbStairs(int n) {
if(n <= 2)
return n;
int* dp = (int*)malloc(sizeof(int)*(n + 1));
dp[0] = 0, dp[1] = 1, dp[2] = 2;
for(int i = 3; i <= n; ++i){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
dp[i]:到达第i阶花费最小力气dp[i]
递归公式:dp[i] = fmin(dp[i-1] + cost[i-1], dp[i-2] +cost[1-2])
初始化:dp[0] = dp[1] = 0 ——可以选择从下标为 0
或下标为 1
的台阶开始爬楼梯,所以说0和1是初始化为0
遍历顺序:从前向后
#include <math.h>
int minCostClimbingStairs(int *cost, int costSize) {
int dp[costSize + 1];
dp[0] = dp[1] = 0;
for (int i = 2; i <= costSize; i++) {
dp[i] = fmin(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
}
return dp[costSize];
}