LeetCode Day動態程式設計第1部分

509. 斐波那契數列

斐波那契數，通常表示為 F(n)，形成一個序列，稱為斐波那契數列，其中每個數都是前兩個數的和，從 0 和 1 開始。即，

F(0) = 0, F(1) = 1
F(n)=F(n-1)+F(n-2)，對於n＞1 1.
給定 n，計算 F(n)。

範例1：

輸入：n = 2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1.
範例2：

輸入：n = 3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2.
範例 3：

輸入：n = 4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3.

限制：

0 原始頁

遞迴法

    public int fib(int n) {
        if(n==0){
            return 0;
        }     
        else if(n==1){
            return 1;
        }   
        else{
            return fib(n-1) + fib(n-2);
        }
    }

遞歸法就像DFS一樣，深入進行，然後回溯得到最終答案。
時間：O(2^n)
空間：O(1)

    private int[] dp = new int[31];
    public int fib(int n) {
        if(n=2 && dp[n]!=0){
            return dp[n];
        }

        dp[n] = fib(n-1) + fib(n-2);
        return dp[n];
    }

我們可以使用全域數組來保存結果，以避免相同元素的重複遞歸。例如下圖顯示 f(17) 和 f(18) 是兩種不同的遞迴路線，如果我們使用正常的遞迴方法，我們必須多次計算它們。

時間：O(n)，空間：O(n)

動態規劃

    public int fib(int n) {
        if(n



<p>遞迴是從上到下再回溯，記憶體遞歸會保存遞迴結果，避免重複計算。現在動態規劃從下到上進行，並將每個步驟的結果儲存到 dp 陣列中。 <br>
時間：O(n)<br>
空間：O(n)</p>
<h2>
  
  
  我們也可以動態更新限制數而不是陣列。這將節省空間複雜度，特別是對於大量元素。
</h2>


<pre class="brush:php;toolbar:false">    public int fib(int n) {
        if(n

<h2>
  
  
  70. 爬樓梯
</h2>

<p>您正在爬樓梯。需要n步才能到達山頂。 </p>

<p>每次可以爬 1 或 2 級階梯。您可以透過多少種不同的方式登上頂峰？ </p>

<p>範例1：</p>

<p>輸入：n = 2<br>
輸出：2<br>
說明：有兩種方法可以登頂。 </p>

<ol>
<li>1 步 + 1 步</li>
<li>2步
範例2：</li>
</ol>

<p>輸入：n = 3<br>
輸出：3<br>
說明：共有三種方法可以登頂。 </p>

<ol>
<li>1 步 + 1 步 + 1 步</li>
<li>1 步 + 2 步</li>
<li>2 步 + 1 步</li>
</ol>
<h2>
  
  
  70. 爬樓梯
</h2>

<p>您正在爬樓梯。需要n步才能到達山頂。 </p>

<p>每次可以爬 1 或 2 級階梯。您可以透過多少種不同的方式登上頂峰？ </p>

<p>範例1：</p>

<p>輸入：n = 2<br>
輸出：2<br>
說明：有兩種方法可以登頂。 </p>

<ol>
<li>1 步 + 1 步</li>
<li>2步
範例2：</li>
</ol>

<p>輸入：n = 3<br>
輸出：3<br>
說明：共有三種方法可以登頂。 </p>

<ol>
<li>1 步 + 1 步 + 1 步</li>
<li>1 步 + 2 步</li>
<li>2 步 + 1 步</li>
</ol>

<p>限制：</p>

<p>1 
原始頁</p>

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172127799096437.png?x-oss-process=image/resize,p_40" class="lazy" alt="Image description" loading="lazy"    style="max-width:90%"  style="max-width:90%"><br>
</p>

<pre class="brush:php;toolbar:false">    public int climbStairs(int n) {
        if(n





<pre class="brush:php;toolbar:false">    public int climbStairs(int n) {
        if(n



<h2>
  
  
  746. 最小成本爬樓梯
</h2>

<p>給定一個整數數組 cost，其中 cost[i] 是樓梯上第 i 步的成本。支付費用後，您可以爬一層或兩層台階。 </p>

<p>您可以從索引 0 的步驟開始，也可以從索引 1 的步驟開始。 </p>

<p>返回到達樓層頂部的最低成本。 </p>

<p>範例1：</p>

<p>輸入：成本 = [10,15,20]<br>
輸出：15<br>
說明：您將從索引 1 開始。 </p>

• 支付 15 美元，爬兩個台階即可到達頂部。 總成本為15。 範例2：

輸入：成本 = [1,100,1,1,1,100,1,1,100,1]
輸出：6
說明：您將從索引 0 開始。

• 支付 1 並爬兩個階梯即可到達索引 2。
• 支付 1 並爬兩個階梯即可到達索引 4。
• 支付 1 並爬兩個階梯即可到達索引 6。
• 支付 1 並爬一級即可達到指數 7。
• 支付 1 並爬兩個階梯即可到達索引 9。
• 支付1並爬一級即可到達頂部。 總費用是6。

限制：

2 0 原始頁

    public int minCostClimbingStairs(int[] cost) {
        if(cost.length 



<h3>
  
  
  請注意，問題告訴我們可以從索引0 和索引1 開始，這意味著如果樓梯數小於2，我們的成本將為0，因為我們可以從該點開始，並且start 的行為將成本為0，只有移動成本的行為。
</h3>


          

            
        

以上是LeetCode Day動態程式設計第1部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！