空間復(fù)雜度可以理解為一段程序在內(nèi)存空間分配了多少，程序使用了多少空間或者內(nèi)存規(guī)模褒墨。相比時(shí)間復(fù)雜度废登，空間復(fù)雜度非常簡單直觀±常空間復(fù)雜度主要通過兩個(gè)特征來把握
1. 數(shù)組的長度
2. 使用了遞歸水评，看遞歸的深度。遞歸深度就是其空間復(fù)雜度
遞歸若結(jié)合了數(shù)組的使用媚送。則看二者誰占用的空間最大中燥，取最大值為空間復(fù)雜度。一般我們認(rèn)為最壞發(fā)生的可能結(jié)果才是最終的結(jié)果塘偎。
舉例：使用了數(shù)組疗涉，在內(nèi)存中分配了一段連續(xù)的存儲(chǔ)空間拿霉。傳入的元素個(gè)數(shù)，就是程序的空間復(fù)雜度咱扣。
例子中绽淘，我存入了int 類型的5個(gè)元素，最后得到這個(gè)數(shù)組n的長度就是5. 這5個(gè)元素在內(nèi)存中就是一段連續(xù)的存儲(chǔ)空間偏窝。所以空間復(fù)雜度o（n）收恢。 n代表元素有多少，就分配多少內(nèi)存祭往。不多不少伦意。
借用LeetCode 70 爬樓梯，來判定程序空間復(fù)雜度
題目：假設(shè)你正在爬樓梯硼补。需要 n?階你才能到達(dá)樓頂驮肉。每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢已骇？注意：給定 n 是一個(gè)正整數(shù)离钝。
示例 1：當(dāng) n = 2 ；答案：兩種方法褪储。
解釋： 第1種方法：1 階 + 1 階 卵渴；第2種方法：直接爬2 階。所以共兩種方法
示例 2：當(dāng)n =?3 鲤竹； 答案：三種方法浪读。
解釋： 有三種方法可以爬到樓頂。
方法1： 1 階 + 1 階 + 1 階辛藻；
方法2：1 階 + 2 階 碘橘；
方法3：2 階 + 1 階。
思路一: 遞歸
爬樓梯問題實(shí)質(zhì)是斐波那契數(shù)列吱肌。很自然想到遞歸來實(shí)現(xiàn)：
想求抵達(dá)第n層的方法痘拆，取決于（n-1）層和（n-2）層方法之和。因?yàn)楫?dāng)爬到第n-1層或者第n-2層氮墨，根據(jù)題目所述纺蛆，下一步都會(huì)是第n層。（因?yàn)橐徊揭徊脚拦婢荆部梢砸淮闻纼蓪樱┯倘觯煌恚琻-1層取決于n-2粒褒，n-3... 以此類推
可是识颊，遞歸構(gòu)建的樹形結(jié)構(gòu)，所有左邊分支都是層數(shù)減1， 右邊分支都是層數(shù)-2祥款。 生成了大量重復(fù)節(jié)點(diǎn)的計(jì)算清笨，且遞歸的深度是n層。 由下圖可以看到刃跛。每一個(gè)f() 占據(jù)一個(gè)內(nèi)存空間抠艾，層層嵌套，直至滿足遞歸的退出條件桨昙，n==0 or n==1 （return 1）检号。所以，用遞歸來解決爬樓梯問題蛙酪，空間復(fù)雜度非常高齐苛。o（n）
思路二：動(dòng)態(tài)規(guī)劃法
動(dòng)態(tài)規(guī)劃算法的核心思想是自底向上的分析問題，先著眼于小問題桂塞，才能解決大問題凹蜂。可以參考代碼的注釋阁危。例子中玛痊，所有的爬樓梯第n層方法，都是從爬一層和爬兩層的方法數(shù)之和算起狂打。
總結(jié)：用動(dòng)態(tài)規(guī)劃法擂煞，我們只是定義了first，second趴乡，third變量对省。并沒有引入數(shù)組，開辟內(nèi)存空間存放數(shù)據(jù)浙宜。也沒有遞歸函數(shù)的出現(xiàn)。一層循環(huán)蛹磺，所以時(shí)間復(fù)雜度是O（n）粟瞬；空間復(fù)雜度是O(1) 常量級(jí)內(nèi)存空間。
