当前位置: 首页 > article >正文

代码随想录算法训练营第51期第32天 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

理论基础

动态规划:dp,每一个状态都是由上个状态推导出来的,因为我是先写完三道题再看理论的,所以有点感概;

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

509. 斐波那契数

509. 斐波那契数icon-default.png?t=O83Ahttps://leetcode.cn/problems/fibonacci-number/

1.因为是n是动态的,所以需要用malloc来分配内存,因为后面会对dp赋值,所以初始化的代码我注释了

2.因为求n,但下标0是从开始的,所以需要n+1

3.这里也可以用递归写,但是复杂度有点2的n次方,我就不记录了

4.我还记录了只需要用2个变量来存储结果的写法,这样就不需要用数组了

动归五部曲

1.确定dp数组以及下标的含义:dp[i]表示第i个斐波那契数

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

3.dp数组如何初始化:dp[0] = 0, dp[1] = 1

4.确定遍历顺序:从前往后遍历

5.举例推导 a = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] ,这里n=10,但是a[10]是第11个斐波那契数,所以需要n+1

int fib(int n) {
    if (n <= 1) {
        return n;
    }
    n = n + 1;
    int *dp = (int*)malloc(sizeof(int) * n);
    // for (int i = 0; i < n; i++) {
    //     dp[i] = 0;
    // }
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i < n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n-1];
}

//这里也可以用递归写,但是复杂度有点2的n次方,我就不记录了 
int fib(int n) {
    if (n <= 1) {
        return n;
    }
    int fir = 0;
    int sec = 1;
    int tmp = 0;
    for (int i = 2; i <= n ; i++) {
        tmp = fir + sec;
        fir = sec;
        sec = tmp;
    }
    return sec;
}

70. 爬楼梯

70. 爬楼梯icon-default.png?t=O83Ahttps://leetcode.cn/problems/climbing-stairs/MD,写在vscode上的东西丢了,我还得再写一次

1.这里和上一题一样,代码也差不多,除了初始化,其他代码都可以复用了。

动归五部曲

1.确定dp数组以及下标的含义:dp[i]表示第i个斐波那契数

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

3.dp数组如何初始化:dp[1] = 1, dp[2] = 2, 这里dp[0]没有意义,但是为了统一,我还是初始化为0

4.确定遍历顺序:从前往后遍历

5.举例推导如下:

1:1

2:1, 2

3:1+1+1,2+1,1+2

4:1+1+1+1,2+1+1,1+2+1,1+1+2,2+2

这里4是第3层再加1和第2层再加2,所以4是第3层和第2层的和,所以dp[4] = dp[3] + dp[2]

int climbStairs(int n) {
    if (n <= 3) {
        return n;
    }
    n = n + 1;
    int *dp = (int *)malloc(sizeof(int) * n);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i < n; i++) {
        dp[i] = dp[i-2] + dp[i-1];
    }
    return dp[n-1];
}


int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    int pre = 1;
    int cur = 2;
    int tmp = 0;
    for (int i = 3; i <= n; i++) {
        tmp = pre + cur;
        pre = cur;
        cur  = tmp;
    }
    return cur;
}

746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯icon-default.png?t=O83Ahttps://leetcode.cn/problems/min-cost-climbing-stairs/1.这一题虽然说简单,但是还真不太容易想到

动归五部曲

1.确定dp数组以及下标的含义:dp[i]表示踏上该楼梯的最小花费(不包括当前楼梯的花费)

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

3.dp数组如何初始化:dp[0] = cost[0], dp[1] = cost[1],这里就不是简单的直接加了,而且后续因为长度只有costSize,和题目要求的顶部还差一点,所以需要再求一次

4.确定遍历顺序:从前往后遍历

5.举例推导:无

#define min(a, b) (((a) < (b)) ? (a) :(b))
int minCostClimbingStairs(int* cost, int costSize) {
    int *dp = (int *)malloc(sizeof(int) * costSize);
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < costSize; i++) {
        dp[i] = min((dp[i-1] + cost[i]), (dp[i-2] + cost[i]));
    }
    int res = min(dp[costSize-2], dp[costSize-1]);
    return res;
}


http://www.kler.cn/a/464081.html

相关文章:

  • 【顶刊TPAMI 2025】多头编码(MHE)之Part 6:极限分类无需预处理
  • 数据结构与算法之动态规划: LeetCode 213. 打家劫舍 II (Ts版)
  • C# 服务调用RFC函数获取物料信息,并输出生成Excel文件
  • C++并发编程之内存顺序一致性
  • AngularJS 过滤器:提升用户体验的数据处理利器
  • DjangoORM字段参数、常用字段类型及参数、模型和表单验证器详解
  • 基于Python的携程旅游景点数据分析与可视化
  • 【C++指针】知识点思维导图
  • 大语言模型提示技巧(二)-给模型时间思考
  • Unity2022接入Google广告与支付SDK、导出工程到Android Studio使用JDK17进行打包完整流程与过程中的相关错误及处理经验总结
  • 【开源免费】基于SpringBoot+Vue.JS音乐网站(JAVA毕业设计)
  • pdf预览 报:Failed to load module script
  • 信息搜集250102
  • 家政服务管理系统|Java|SSM|VUE| 前后端分离
  • 分布式 L2 网关下的 OVS 未知单播泛洪
  • 【设计模式】 基本原则、设计模式分类
  • 【安卓开发】【Android Studio】项目构建失败提示【Could not read metadata.bin】解决方法
  • 2025年,测试技能支棱起来。
  • 每天40分玩转Django:Django安全专题
  • 【GIT(命令)基础操作笔记--关于本地仓库】
  • Kafka系列教程 - Kafka 消费者 -3
  • 数据挖掘——朴素贝叶斯分类
  • 滑动窗口——将x减到0的最小的操作数
  • 长时间序列预测算法---Informer
  • Cocos游戏中集成RichTap高品质振动
  • SpringCloud微服务架构