版本一：一维数组记录型
class Solution {
public:
int fib(int n) {
if(n dp(n+1);
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i
利用一维数组进行记录。目的 明确动态规划的 的五步
- 确定dp数组的含义
- 确定递推公式
- 初始化问题
- 遍历问题
- 日志问题
版本二：两个变量记录
class Solution {
public:
int fib(int n) {
if(n
因为每一次都只用到前面两个的数据，因此可以简化数组。降低空间复杂度。
版本三：递归
class Solution {
public:
int fib(int n) {
if(n
使用自顶向下的进行计算，中间存在重叠的子问题。可以利用一个数组进行记忆化搜索。
版本一：空间没有优化的版本
class Solution {
public:
int climbStairs(int n) {
if(n dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i
确定五部曲，明确每一步含义。
版本二：优化空间
class Solution {
public:
int climbStairs(int n) {
if(n
因为每一次都只是用到前面两个dp的值，返回的也只是一个对应的dp值，所以可以进行空间的优化。
版本一：没有进行空间优化
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
int height = cost.size();
if(height == 1) return cost[0];
vector dp(height);
dp[0] = cost[0];
dp[1] = cost[1];
for(int n = 2 ; n < height; ++n){
dp[n] = min(dp[n-1] , dp[n-2] ) + cost[n] ;
}
return min(dp[height-1] , dp[height - 2]);
}
};
版本二： 空间优化
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
int height = cost.size();
if(height == 1) return cost[0];
int dp[2] ;
dp[0] = cost[0];
dp[1] = cost[1];
int dp3 = 0;
for(int n = 2 ; n < height; ++n){
dp3 = min(dp[1] , dp[0] ) + cost[n] ;
dp[0] = dp[1];
dp[1] = dp3;
}
return min(dp[1] , dp[0]);
}
};
Original: https://www.cnblogs.com/sansuitaibai/p/16704194.html
Author: sansuitaibai
Title: 1. 斐波那契数 爬楼梯 使用最少花费爬楼梯
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/577621/
转载文章受原作者版权保护。转载请注明原作者出处！