1、正常跳台階
一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法(先後次序不同算不同的結果)。
大體思路：
第 i 個樓梯可以從第 i-1 和 i-2 個樓梯再走一步到達，即走到第 i 個樓梯的方法數為走到第 i-1 和第 i-2 個樓梯的方法數之和。是以可以推導出遞推公式為：dp[i]=dp[i-1]+dp[i-2]
考慮到 dp[i] 隻與 dp[i - 1] 和 dp[i - 2] 有關，是以可以隻用兩個變量來存儲 dp[i - 1] 和 dp[i - 2]，使得原來的 O(N) 空間複雜度優化為 O(1) 複雜度。具體非遞歸代碼如下：++++++++++++++++++++++++++
2、變态跳台階
一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。
大緻思路：
(1)每一個高度的台階都可以一步完成，是以每一個位置都有一種基本解 dp[i]=1
(2)除了基本解之外，每一個高度的完成解還受到且僅受到前一個相鄰高度dp[i-1]的影響。
(3)是以，每一個高度的最終解都是前一個數的解()+本身的基本解。即，dp[i]=1+dp[i-1];
3、搶劫一排房子
你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。
大體思路：
(1)相鄰的房間不可以偷==》偷了i就不可以偷i-1.
(2)那麼假如i為一排房間的最後一間，那麼走過目前i個房間的最大值為：
dp[i]=max(dp[i-2]+numms[i],dp[i-1]);
是以，也需要兩個值dp[i-1],dp[i-2]。
4、搶劫一圈房子(環形的第一家和最後一家是相鄰的)
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房内都藏有一定的現金。這個地方所有的房屋都圍成一圈，這意味着第一個房屋和最後一個房屋是緊挨着的。同時，相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。
解題思路：
5、大牛生小牛問題
假設農場中成熟的母牛每年都會生 1 頭小母牛，并且永遠不會死。第一年有 1 隻小母牛，從第二年開始，母牛開始生小母牛。每隻小母牛 3 年之後成熟又可以生小母牛。給定整數 N，求 N 年後牛的數量。
思路：
(1)在前三年，隻有母牛才可以生産。
(2)因為所有的牛都不會死，是以，第N-1年的所有牛dp[N-1]都會活到第N年。
(3)因為成熟的母牛每年都會生 1 頭小母牛。是以，第N-3年中的所有牛到第N年都會新增一個小母牛。dp[N-3]。
N 年後牛的總數量為：一直的大母牛dp[N-1]+新增的小母牛dp[N-3]。
6、矩陣覆寫問題
我們可以用2*1的小矩形橫着或者豎着去覆寫更大的矩形。請問用n個2*1的小矩形無重疊地覆寫一個2*n的大矩形，總共有多少種方法？
思路類似于正常跳台階。
希望能夠對需要的小夥伴們有幫助！願小夥伴們越來越強大！
“我是一名從事了10年開發的高齡程式員，最近我花了一些時間整理了一個完整的學習C語言、C++的路線，項目源碼和工具。對于想學習C/C++的小夥伴而言，學習的氛圍和志同道合的夥伴很重要，筆者推薦我專欄的C語言/C++程式設計愛好者的聚集地>>>C語言/C++進階之路 - 專題 - 簡書！
歡迎初學和進階中的小夥伴！工作需要、感興趣、為了入行、轉行需要學習C/C++的夥伴可以一起學習！”
喜歡小編的記得動動您的小指點個關注喲！