首页 > 其他分享 >【DP】LeetCode 70. 爬楼梯

【DP】LeetCode 70. 爬楼梯

时间:2023-04-02 13:36:09浏览次数:55  
标签:pre 台阶 int DP 70 LeetCode dp pre2

题目链接

70. 爬楼梯

思路

分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律

表示状态

假设走到了最后一层台阶,考虑一下我们要存储的信息:

  • 走到这最后一层台阶的方法数
  • 当前台阶数,用于判断是否走到了最后一层台阶

这时候很容易想到使用一维数组 dp[i] 来表示走到第 i 层台阶有多少种方法。

找状态转移方程

在第 i 层台阶处,我们可以看作两种情况:

  • 从第 i-1 层台阶走了一步到第 i 层
  • 从第 i-2 层台阶走了两步到第 i 层

这样可以得到状态转移方程

\[dp[i] = dp[i - 1] + dp[i - 2] \]

边界处理

很容易知道 dp[1] = 1dp[2] = 2

空间优化

因为 dp[i] 只与 dp[i - 1]dp[i - 2] 有关,所以可以使用两个单变量 prepre2 分别表示 dp[i - 1]dp[i - 2],同时不断滚动更新。

代码

dp数组版

class Solution {
    public int climbStairs(int n) {
        // dp[i] = dp[i - 1] + dp[i - 2]
        int[] dp = new int[n + 3];
        dp[1] = 1;
        dp[2] = 2;

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

        return dp[n];
    }
}

空间优化版

class Solution {
    public int climbStairs(int n) {
        // dp[i] = dp[i - 1] + dp[i - 2]
        int pre = 1;
        int pre2 = 2;
        int result = pre + pre2;
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }

        for(int i = 3; i <= n; i++){
            result = pre + pre2;
            pre = pre2;
            pre2 = result;
        }

        return result;
    }
}

标签:pre,台阶,int,DP,70,LeetCode,dp,pre2
From: https://www.cnblogs.com/shixuanliu/p/17280294.html

相关文章

  • [LeetCode] 1338. Reduce Array Size to The Half 数组大小减半
    Youaregivenanintegerarray arr.Youcanchooseasetofintegersandremovealltheoccurrencesoftheseintegersinthearray.Return theminimumsizeofthesetsothat atleast halfoftheintegersofthearrayareremoved.Example1:Input:arr=......
  • HJ70_矩阵乘法计算量估算_入门栈使用的典型题
    反思:这题咋一看不难,但是越做坑越多,按照一开始不完善的思路无法完全通过测试。参看高赞答案,代码行数特少。但是没考虑一个括号中有三个矩阵的情况。思路:1、判断哪两个矩阵开始相乘的条件:遇到“)”时,该字符前两个矩阵开始相乘。把相乘后矩阵行列数组压入栈栈中。该题默认不存在(A(......
  • Leetcode(剑指offer专项训练)——DP专项(4)
    加减的目标值给定一个正整数数组nums和一个整数target。向数组中的每个整数前添加 '+'或'-',然后串联起所有整数,可以构造一个表达式:例如,nums=[2,1],可以在2之前添加'+',在1之前添加'-',然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算......
  • 代码随想录Day17-Leetcode110.平衡二叉树,257. 二叉树的所有路径,404.左叶子之和
    110.平衡二叉树题目链接:https://leetcode.cn/problems/balanced-binary-tree/一个显然但似乎不太高效的方法是:通过递归获取左右子树高度,判断差;然后递归判断左右结点;那么一个显然的改进就是后序遍历/***Definitionforabinarytreenode.*functionTreeNode(val......
  • 关于网络通信中TCP/UDP的端口范围-以及在Linux系统中的使用权限说明
    关于TCP/UDP的端口号的范围都是0~65535 根据IANA定义,可以参考如下链接:https://www.iana.org/assignments/service-names-port-numbers/service-names-port-numbers.xhtmlIANA将这些端口分成了3类,LastUpdated2023-03-30Portnumbersareassignedinvariousways,based......
  • 调试freeradius时遇到的 线程池以及udp相关问题
    调试线程池过程中遇到了一个return和pthread_exit的问题;google一下发现右如下概念首先,return语句和pthread_exit()函数的含义不同,return的含义是返回,它不仅可以用于线程执行的函数,普通函数也可以使用;pthread_exit()函数的含义是线程退出,它专门用于结束某个线程的执行。在主......
  • leetcode876. 链表的中间结点
      876. 链表的中间结点方法一:最简单的做法,先求出整个链表的长度,再求1/2处节点的位置。/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx)......
  • leetcode-733-easy
    FloodFillAnimageisrepresentedbyanmxnintegergridimagewhereimage[i][j]representsthepixelvalueoftheimage.Youarealsogiventhreeintegerssr,sc,andcolor.Youshouldperformafloodfillontheimagestartingfromthepixelimage[sr......
  • leetcode-724-easy
    FindPivotIndexGivenanarrayofintegersnums,calculatethepivotindexofthisarray.Thepivotindexistheindexwherethesumofallthenumbersstrictlytotheleftoftheindexisequaltothesumofallthenumbersstrictlytotheindex's......
  • leetcode-744-easy
    FindSmallestLetterGreaterThanTargetYouaregivenanarrayofcharacterslettersthatissortedinnon-decreasingorder,andacharactertarget.Thereareatleasttwodifferentcharactersinletters.Returnthesmallestcharacterinlettersthatis......