代码随想录第三十三天(一刷&&C语言)|斐波那契数&&爬楼梯&&使用最小花费爬楼梯

2023-12-15 22:41:33

创作目的:为了方便自己后续复习重点,以及养成写博客的习惯。

动态规划步骤:

  1. 确定dp数组以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

一、斐波那契数

思路:参考carl文档

1、dp[i]的定义为:第i个数的斐波那契数值是dp[i]。

2、递推公式为:?dp[i] = dp[i - 1] + dp[i - 2]。

3、dp数组初始化:dp[0] = 0,dp[1] = 1。

4、从递归公式可以看出,dp[i]是依赖于 dp[i - 1] 和 dp[i - 2],遍历的顺序为从前到后遍历。

5、自己模拟推到dp数组,debug的时候添加打印。

ledcode题目:https://leetcode.cn/problems/fibonacci-number/

AC代码:

int fib(int n){
    //当n <= 1时,返回n
    if(n <= 1)
        return n;
    //动态开辟一个int数组,大小为n+1
    int *dp = (int *)malloc(sizeof(int) * (n + 1));
    //设置0号位为0,1号为为1
    dp[0] = 0;
    dp[1] = 1;

    //从前向后遍历数组(i=2; i <= n; ++i),下标为n时的元素为dp[i-1] + dp[i-2]
    int i;
    for(i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

二、爬楼梯

思路:参考carl文档

1、dp[i]的定义为: 爬到第i层楼梯,有dp[i]种方法。

2、确定递推公式:dp[i] = dp[i - 1] + dp[i - 2] 。

3、dp数组初始化:不初始化dp[0],只初始化dp[1] = 1,dp[2] = 2,从i = 3开始递推。

4、从递推公式可知遍历顺序是从前向后遍历。

5、举例当n为4的时候,dp[4] = 5。

lecode题目:https://leetcode.cn/problems/climbing-stairs/description/

AC代码:

int climbStairs(int n){
    //若n<=2,返回n
    if(n <= 2)
        return n;
    //初始化dp数组,数组大小为n+1
    int *dp = (int *)malloc(sizeof(int) * (n + 1));
    dp[0] = 0, dp[1] = 1, dp[2] = 2;

    //从前向后遍历数组,dp[i] = dp[i-1] + dp[i-2]
    int i;
    for(i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    //返回dp[n]
    return dp[n];
}

三、使用最小花费爬楼梯

思路:参考carl文档

1、dp[i]的定义为:到达第i台阶所花费的最少体力为dp[i]。

2、确定递推公式为:dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。

3、dp数组初始化:dp[0] = 0,dp[1] = 0。

4、dp[i]由dp[i-1]dp[i-2]推出,故从前到后遍历cost数组。

5、举例推导dp数组(模拟一组cost)

ledcode题目:https://leetcode.cn/problems/min-cost-climbing-stairs/description/

AC代码:

#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];
}

全篇后记:

? ? ? ? 开启全新篇章动态规划,之前有刷过但是不成体系,希望能一刷掌握思路与方法,给后面的刷题打下坚实的基础。

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