斐波那契數列模型----三步問題

面試題 08.01. 三步問題 - 力扣(LeetCode)

1、狀態表示

題目要求:上到n階臺階,有多少種方法。那么n逐漸簡化,上1階臺階有多少種方法;上2階臺階有多少種方法……直到上n階臺階有多少種方法。

那么,狀態表示dp[i]:上n階臺階有多少種方法。

2、狀態轉移方程

上1階臺階:從地面到1,0-》1。1種方法,dp[1] = 1

上2階臺階:從地面到2,0-》2;或者從1到2,0-》1-》2。2兩種方法,dp[2] = 2

上3階臺階:0-》3;或者0-》1-》3;或者0-》1-》2-》3;或者0-》2-》3。4種方法。dp[3] = 4

上4階臺階:1-》4;2-》4,3-》4。那么從1-》4,就先需要上1階臺階,1種方法;從2-》4,就先需要上2階臺階,2種方法;從3-》4,就先需要上3階臺階,4種方法。一共dp[4] = 7,dp[4] = dp[1] + dp[2] + dp[3]。

……

那么,要想走到第i階臺階,就有三種情況:從i-1直接到i,從i-2直接到i,從i-3直接到i。

那么求走到第i階臺階的方法dp[i],就應該先知道dp[i-1],dp[i-2],dp[i-3],那么dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

3、初始化

由狀態轉移方程可知,至少需要初始化前三個狀態。

那么,地面可認為dp[0],那么dp[0]應該如何初始化呢?其實這里初始化0或1都沒有關系,因為o0或1都可以解釋得通。

我這里就初始化為1了。因為從0-》3,是一種方法,那么dp[3] = dp[0] + dp[1] + dp[2],方便寫代碼。

4、遍歷順序

顯然就是從左到右遍歷。

5、返回值

那么就是dp[n]。

class Solution {
public:int waysToStep(int n) {//越界檢查if(n == 1 || n == 0) return 1;if(n == 2) return 2;const int MOD = 1e9 + 7;vector<int> dp(n+1);//創建dp表dp[0] = dp[1] = 1,dp[2] = 2;//初始化for(int i = 3;i<=n;i++)//遍歷順序dp[i] = ((dp[i-1] + dp[i-2])%MOD + dp[i-3])%MOD;//狀態轉移return dp[n];}
};

同樣這里也可以用滾動數組優化。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/717651.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/717651.shtml
英文地址,請注明出處:http://en.pswp.cn/news/717651.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

c++ [[nodiscard]]關鍵字詳解

如果一個函數聲明了[[nodiscard]]&#xff0c;則該函數的返回值不能沒有承接&#xff0c;如果沒有承接&#xff0c;就會編譯報warning [[nodiscard]]是c17新特性&#xff0c;但本地用c11標準編譯也能編譯過&#xff0c;尚不清楚原因&#xff0c;c20加入了warning后的額外文字描…

代碼隨想錄第45天|● 70. 爬樓梯 (進階) ● 322. 零錢兌換 ● 279.完全平方數

文章目錄 ● 70. 爬樓梯 &#xff08;進階&#xff09;思路&#xff1a;- 排列 先value后weight代碼&#xff1a; ● 322. 零錢兌換思路&#xff1a;代碼 ● 279.完全平方數思路&#xff1a;代碼 ● 70. 爬樓梯 &#xff08;進階&#xff09; 思路&#xff1a;- 排列 先value后…

如何提升計算機性能

04 穿越功耗墻&#xff0c;我們該從哪些方面提升“性能”&#xff1f; 上一講&#xff0c;在講 CPU 的性能時&#xff0c;我們提到了這樣一個公式&#xff1a; 程序的 CPU 執行時間 指令數CPIClock Cycle Time 這么來看&#xff0c;如果要提升計算機的性能&#xff0c;我們可以…

zookeeper框架

事務ID Znode的創建刪除&#xff0c;更改內容等都是作為zookeeper的事務進行執行的。 對于每一個事務請求&#xff0c;zookeeper都會為其分配一個全局唯一的事務ID&#xff0c;從ID可以識別出事務的全局順序。 節點特性 czxid:create zxid,數據節點創建時的事務ID mzxid&…

基于ZYNQ的PCIE高速數據采集卡的設計(一)

作為信息處理的第一步&#xff0c;數據采集的作用越來越重要。目前&#xff0c;數據采集已經在航 空、民用、軍事、醫療等領域得到廣泛應用。隨著相關技術的不斷發展&#xff0c;信號頻率越 來高&#xff0c;帶寬越來越大&#xff0c;使得數據采集技術逐漸向高速大數據的方向…

【python】優化docker鏡像體積

背景 測試腳本的最終所構成的鏡像體積偏大&#xff0c;項目提出整改 實現思路 1.測試基礎鏡像&#xff0c;更換為更小的 參見&#xff1a;python 多階段構建docker鏡像&#xff0c;有效減少鏡像大小 - 知乎 2.去掉實際未使用的依賴庫

幻獸帕魯專用服務器搭建之Linux部署配置教程

大家好我是飛飛&#xff0c;上一期我分享了Windows系統的幻獸帕魯服務器搭建教程。因為幻獸帕魯這游戲對服務器的配置有一定的要求&#xff0c;很多小伙伴就尋思用Linux系統搭建占用會不會小一點&#xff1f;有計算機基礎的小伙伴都知道Linux系統和Windows系統相比&#xff0c;…

【Linux】實時查看服務器信息

查看服務器CPU使用率 使用命令mpstat 1。這里的1表示每隔1秒更新一次CPU使用率。如果系統未安裝mpstat&#xff0c;可以通過安裝sysstat包來獲取它。 在基于Debian的系統&#xff08;如Ubuntu&#xff09;上&#xff0c;使用命令&#xff1a; sudo apt-get update sudo apt-…

JavaScript 數據類型詳解的教程

在JavaScript中&#xff0c;數據類型是非常重要的概念&#xff0c;了解數據類型有助于我們更好地操作數據以及編寫高效的代碼。本教程將詳細介紹JavaScript中的各種數據類型&#xff0c;包括基本數據類型和復雜數據類型。 基本數據類型 1. 數值(Number) 在JavaScript中&…

考研復試類比社團招新,無所謂“公平”,導師選誰都是他的權力

這篇文章是抖音和b站上上傳的同名視頻的原文稿件&#xff0c;感興趣的csdn用戶可以關注我的抖音和b站賬號&#xff08;GeekPower極客力量&#xff09;。同時這篇文章也為視頻觀眾提供方便&#xff0c;可以更加冷靜地分析和思考。文章同時在知乎發表。 我考研一戰的時候計算機考…

MySQL 主從復制配置指南

MySQL 主從復制配置指南 MySQL主從復制允許數據從一個MySQL數據庫服務器&#xff08;主服務器&#xff09;復制到一個或多個MySQL數據庫服務器&#xff08;從服務器&#xff09;。這是一種常用的數據冗余和備份方法&#xff0c;也可以用于負載均衡。 前提條件 主服務器和從服…

【詳識JAVA語言】面向對象程序三大特性之一:封裝

封裝的概念 面向對象程序三大特性&#xff1a;封裝、繼承、多態。而類和對象階段&#xff0c;主要研究的就是封裝特性。何為封裝呢&#xff1f;簡單來說 就是套殼屏蔽細節。 比如&#xff1a;對于電腦這樣一個復雜的設備&#xff0c;提供給用戶的就只是&#xff1a;開關機、通…

飛槳模型轉ONNX模型教程

文章目錄 飛槳模型轉ONNX模型教程1. ONNX簡介2. Paddle2ONNX安裝3. 獲取Paddle2ONNX模型庫4. 飛槳轉ONNX教程4.1 飛槳訓練模型導出為ONNX模型4.2 飛槳部署模型轉為ONNX模型4.3 驗證ONNX模型4.4 使用ONNX模型進行推理 5. 注意事項 飛槳模型轉ONNX模型教程 1. ONNX簡介 ONNX是一…

管理系統提升:列表頁構成要素,拒絕千篇一律

大家伙&#xff0c;我是大千UI工場&#xff0c;專注UI知識案例分享和接單&#xff0c;本期帶來B端系統列表頁的分享&#xff0c;歡迎大家關注、互動交流。 一、什么是列表頁 管理系統列表頁是指管理系統中用于展示和管理數據的頁面&#xff0c;通常以表格或列表的形式呈現。列…

【appium】APP元素操作Api、androidDriver操作Api

一、元素操作Api 主要是做斷言 text 1、click()——觸發當前元素的點擊事件 2、sendKeys(...)——輸入數據 3、clear()——清空內容 4、getAttribute() ——獲取屬性值 字符串類型屬性&#xff1a; content-desc&#xff08;返回content-desc屬性值&#xff09; text(返…

C語言中結構體成員訪問操作符的含義及其用法

1.直接訪問操作符 用法&#xff1a;結構體名.成員名。 含義&#xff1a;直接訪問結構體中的成員變量。 示例&#xff1a; #include<stdio.h> struct student {char name[20];int age; }; int main() {//定義了一個結構體數組arrstruct student arr[4] { {"cxk&q…

產品經理相關的學習網站

一、原型案例 AxureShop產品原型網&#xff1a; https://www.axureshop.com/ 人人都是產品經理&#xff1a;https://www.woshipm.com/ 二、如何找各類圖標、各類圖表 各類圖標&#xff1a; IconPark&#xff1b; 各類圖表&#xff1a;echarts.apache.org&#xff08;柱狀圖、餅…

深入淺出HTTP/2預檢請求(CORS Preflight Request)

前言 在現代Web開發中&#xff0c;跨域資源共享&#xff08;Cross-Origin Resource Sharing&#xff0c;簡稱CORS&#xff09;是一項關鍵技術&#xff0c;它允許瀏覽器在不同源之間安全地執行Ajax請求。當一個來自不同源的請求涉及到一些特殊 HTTP 頭部或者方法時&#xff0c;…

23端口登錄的Telnet命令+傳輸協議FTP命令

一、23端口登錄的Telnet命令 Telnet是傳輸控制協議/互聯網協議&#xff08;TCP/IP&#xff09;網絡&#xff08;如Internet&#xff09;的登錄和仿真程序&#xff0c;主要用于Internet會話。基本功能是允許用戶登錄進入遠程主機程序。 常用的Telnet命令 Telnet命令的格式為&…

有人吐槽:可視化大屏面向領導的設計,真相是這樣嗎?

某些老鐵的態度很極端&#xff0c;看到可視化大屏頁面就一口斷定&#xff0c;除了討好領導之外&#xff0c;屁用沒有。真相是這樣嗎&#xff1f;貝格前端工場嘗試給老鐵們分析下。 一、可視化大屏確實要面向領導&#xff0c;但不是討好領導 可視化大屏的設計需要考慮領導和管理…