首页 > 编程语言 >Java数据结构与算法(爬楼梯动态规划)

Java数据结构与算法(爬楼梯动态规划)

时间:2024-06-09 12:31:54浏览次数:23  
标签:爬楼梯 int Solution public return Java 数据结构 class dp

前言

爬楼梯就是一个斐波那契数列问题,采用动态规划是最合适不过的。

实现原理

初始化:dp[0]=1;dp[1]=2;

转移方程:dp[i]=dp[i-1]+d[i-2];

边界条件:无

具体代码实现

class Solution {
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        int[] dp=new int[n];
        dp[0]=1;
        dp[1]=2;
        for(int i=2;i<n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n-1];
    }
}

QA:内存占用是否可以继续优化?

具体代码实现(通过2个int变量的轮换完成内存的优化)

class Solution {
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        int a=1;int b=2;
        for(int i=2;i<n;i++){
            int temp=a+b;
            a=b;
            b=temp;
        }
        return b;
    }
}

标签:爬楼梯,int,Solution,public,return,Java,数据结构,class,dp
From: https://blog.csdn.net/acuteeagle01/article/details/139538331

相关文章

  • JAVAEE之网络编程(1)_套接字、UDP数据报套接字编程及从代码实例
    前言什么是网络编程呢? 网络编程,指网络上的主机,通过不同的进程,以编程的方式实现网络通信(或称为网络数据传输)。当然,即便是同一个主机,只要是不同进程,基于网络来传输数据,也属于网络编程一、网路编程中的基本概念1.1发送端和接收端发送端:数据的发送方进程,称为发送端。发......
  • 数据结构---树与二叉树
    个人介绍hellohello~,这里是code袁~......
  • java springboot 网页时装购物系统在线网上平台网站程序源代码+论文
    !!!有需要的小伙伴可以通过文章末尾名片咨询我哦!!! ......
  • 跨语言系统中的功能通信:Rust、Java、Go和C++的最佳实践
    在现代软件开发中,使用多种编程语言构建复杂系统已成为一种常见的做法。每种编程语言都有其独特的优势和适用场景,这使得在同一个系统中使用多种语言变得合理且高效。然而,这也带来了一个重要的挑战:如何在这些不同语言之间实现高效、可靠的功能通信。本文将探讨Rust、Java、Go和C+......
  • Java项目源码文案PPT讲解基于springboot框架的酒店管理
    !!!有需要的小伙伴可以通过文章末尾名片咨询我哦!!! ......
  • 如何通过javascript自动增加markdown h1的文本内容?
    背景希望美化博客园博客,至少不希望文本那么密集地显示,而且想自动在headline插入表情符号,自动进行目录和文本缩进等等。问题如何通过javascript自动增加markdownh1的文本内容?方案在html中增加如下js脚本即可。document.addEventListener("DOMContentLoaded",function(){......
  • [Java] Mybatis向Mysql插入主副表JSON数据
    ......
  • Apache POI(使用Java读写Excel表格数据)
    1.ApachePOI简介ApachePOI是一个开源的Java库,用于操作MicrosoftOffice格式的文件。它支持各种Office文档的读写功能,包括Word文档、Excel电子表格、PowerPoint演示文稿、Outlook电子邮件等。ApachePOI提供了一组API,使得Java开发者能够轻松地在Java应用程序中处理Office文件......
  • 数据结构与算法之归并排序,以及它的代码实现与事例
    目录前言定义策略代码实现结果结束语前言今天是坚持写博客的第22天,我们来看看数据结构与算法当中的归并排序。定义首先我们来看看什么是归并排序?归并排序(MergeSort)是一种分治思想的排序算法。它将待排序的数组分成若干个子数组,每个子数组都是有序的,然后再将有序......
  • 【java】JVM前端编译器的局限性
    目录1.不涉及编译优化2.功能限制3.静态编译特性4.与AOT编译器的对比1.不涉及编译优化1.前端编译器的主要任务是将符合Java语法规范的Java代码转换为符合JVM规范的字节码文件2.并不会直接涉及编译优化等方面的技术。3.具体的优化细节通常是由HotSpot的JIT(Jus......