資訊專欄INFORMATION COLUMN
摘要：題目假設(shè)你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個題目只要模擬一下基本就能想到是，狀態(tài)方程寫出來就是斐波那契數(shù)列。
題目
假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數(shù)。
示例 1：
輸入： 2 輸出： 2 解釋： 有兩種方法可以爬到樓頂。 1. 1 階 + 1 階 2. 2 階
示例 2：
輸入： 3 輸出： 3 解釋： 有三種方法可以爬到樓頂。 1. 1 階 + 1 階 + 1 階 2. 1 階 + 2 階 3. 2 階 + 1 階題解
這個題目只要模擬一下基本就能想到是TP，狀態(tài)方程寫出來就是斐波那契數(shù)列。
dp[i] = dp[i-1] + dp[i-2]
i-1的時候跳一步可以到達i
i-2的時候跳一步是i-1，這個變成dp[i-1]的子問題了,直接跳兩步可以到達i
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
python
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
dp = [1 for i in range(n + 1)]
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
熱門文章
【Spring】IOC是啥有什么好處
【Leetcode】67. 二進制求和
【Leetcode】66. 加一
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/35970.html
摘要：題目假設(shè)你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個題目只要模擬一下基本就能想到是，狀態(tài)方程寫出來就是斐波那契數(shù)列。 題目 假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。 每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個正整數(shù)。 示...
摘要：題目假設(shè)你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個題目只要模擬一下基本就能想到是，狀態(tài)方程寫出來就是斐波那契數(shù)列。 題目 假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。 每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個正整數(shù)。 示...
摘要：小鹿題目假設(shè)你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。算法思路二種解決思路，第一利用遞歸第二利用動態(tài)規(guī)劃。就是因為有了重復(fù)元素的計算，導(dǎo)致了時間復(fù)雜度成指數(shù)的增長。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿 題目：Climbing Stairs You a...
摘要：題目要求假設(shè)有級臺階為正整數(shù)，每次可以爬一級臺階或兩級臺階。問有多少種方法爬完級臺階遞歸方法最后一步可以是一級臺階，或者是兩級臺階，一共兩種情況。 題目要求：假設(shè)有n級臺階（n為正整數(shù)），每次可以爬一級臺階或兩級臺階。問有多少種方法爬完n級臺階？ 遞歸方法最后一步可以是一級臺階，或者是兩級臺階，一共兩種情況?？赏ㄟ^遞歸獲得n-1級臺階和n-2級臺階的和獲得n級臺階的結(jié)果臺階數(shù)量過高的話...
閱讀 2075·2023-04-25 22:58
閱讀 1427·2021-09-22 15:20
閱讀 2706·2019-08-30 15:56
閱讀 1999·2019-08-30 15:54
閱讀 2117·2019-08-29 12:31
閱讀 2741·2019-08-26 13:37
閱讀 605·2019-08-26 13:25
閱讀 2107·2019-08-26 11:58
