day 38 动态规划(1)

2024-01-07 18:55:04

day38
代码随想录
2024.1.6
开始动态规划!
递归五部曲:

  1. 确定dp数组含义
  2. 确定递推公式
  3. dp数组初始化
  4. 遍历顺序
  5. 举例推导dp数组

1. 50斐波那契数列
经典的动态规划入门第一题,直接递归五部曲,

  1. 本题递归数组是具体要求的值,而dp数组下标则是所给参数n
  2. 根据题目要求,递推公式应该为,从第三个数开始,每个数等于前两个数之和
  3. dp初始化本题题目已给
  4. 根据递归公式,遍历顺序为从左往右
  5. n=0,n=1,然后n=2值为前两个之和为1,以此类推。
class Solution {
public:
    int fib(int n) {
        if(n<=1)
            return n;
        vector<int> DP(n+1);
        DP[0] = 0;
        DP[1] = 1;
        
        for(int i=2;i<=n;i++){
            DP[i] = DP[i-1] + DP[i-2];
        }
        return DP[n];
    }
};

2. 70爬楼梯

  1. 首先,本题dp数组含义是有多少种爬楼梯的方法,而下标n表示楼梯阶数
  2. 这道题递推公式得稍微思考一下,首先针对一个阶梯为n得,最后一步是能走一步或两步,走一步时前一步就是n-1层,走两步前一层就是n-2层,因为,阶梯为n的无非就两种情况,加起来就好,会发现,跟斐波那契数列递推公式相同
  3. 本题不存在n=0,n=1和n=2就是初始化值
  4. 同理,从左往右
  5. 类比斐波那契数
class Solution {
public:
    int climbStairs(int n) {
        if(n<=2) return n;
        vector<int> dp(n+1);
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;i<=n;i++)
            dp[i] = dp[i-1] + dp[i-2];
        return dp[n];
    }
};

3. 746使用最小代价爬楼梯
这道题初始化开始没有弄清楚

  1. dp数组为最小花费,i是楼梯数
  2. 与爬楼梯类似,i楼梯是i-1和i-2楼梯而来,不过,此时不是相加,因为要求最小花费,而dp[i-1]是到达该层的花销,要加上之后的开销cost[i-1],i-2也是一样,然后在这两种情况中找最小值
  3. 这是开始没弄清的情况,0和1开始的不用花费因此都是0
  4. 当然还是从左往右
  5. 略!
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size() + 1);
        dp[0] = 0; 
        dp[1] = 0;
        for (int i = 2; i <= cost.size(); i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.size()];
    }
};

文章来源:https://blog.csdn.net/qq_56913257/article/details/135425504
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。