我是一個學c++的學生，最近在學到區間動態規劃的時候對於這個演算法的理解是到位了，可是代碼卻始終理解不了。還有很多遞歸的代碼，腦子像是卡住了一樣，想也想不通，這是我的天賦問題嗎？

平均智商的人都能學會C++。只不過新手很容易走進誤區。最常見的誤區就是一開始就追求什麼都理解。「看不懂怎麼辦」、」聽不懂怎麼辦「這類問題一大堆人問。

想不通就不要想，先注重模仿而不是理解。就像嬰兒跟父母學說話一樣，如果嬰兒每句話都要去理解，那永遠都學不會了。

初學計算機語言的人也是一樣，在編程語言面前就是個嬰兒，那就把自己當成嬰兒，不要管什麼意思。等自己真的變成了大人，自然能懂的就越來越多。

小學生更容易學會C++，因為他們不會去想怎麼理解不了。

說一下自己的感受。

計算機科學往往是由一些非常簡單的知識疊加為一個非常複雜的體系。比如遞歸，分形。

理解這些的時候往往自己會陷入其中，所謂的身在廬山吧。

所以，我的一點經驗是兩個，一個簡化輸入的數據，比如遞歸河內塔，要理解每一步執行的過程，如果上來就輸入10個20個盤子，一開始就會亂掉，所以一開始可以輸入2個盤子，3個盤子。步驟少了後自然容易理解。

第二個經驗大而化之。不去了解每條語句的執行過程，而去把整個模塊的執行當作一個單元。從這兩個角度去了解，有時候往往會讓你有不一樣的感覺。

對於遞歸的理解

return_type recursive_function(para_type param) {
// 1. 優先處理遞歸的base case
// 備註: base case可能不止一種, 在分析問題畫遞歸樹時確認其數量
if (satisfy_base_condition1) {
return base_case_value1;
}
// ...

// 2. 處理normal case, 遞歸的調用自身
// 備註: 求解問題的規模得到縮減，直至base case
// ...
return normal_case_value;
}

對於動態規劃的理解

  1. 遞歸演算法解決問題
  2. 發現1中有重複計算，使用記憶化遞歸消除重複計算
  3. 對2的嵌套函數調用可能產生爆棧、調用開銷不滿意，改寫成 dp數組存儲空間+迭代的方式（用熟練了就能直接使用3，寫出1和2是為了加深理解）

備註:

  • 2其實已經是DP了
  • 3的方式實現是：
    • 開闢數組空間用於記錄不同問題規模的結果 (待填充)
    • 將base case的結果填入dp數組
    • 按問題規模從小到大的順序依次將結果填入dp數組
  • 3的本質是: 手動的逆序展開了2中的遞歸，理解"當前規模問題的結果依賴於更小規模問題的結果"是重點。

實用Tips - 題目強烈暗示使用動態規劃的情況

  • 是否能夠XXXX/方案數是多少?
  • 最大/最小XXXX是多少?
  • prefix sum / presum array
  • ....

當然，理解動規的思想+熟悉了動規套路可以無視以上Tips。

多刷幾道題就會了，以絕大多數人的努力程度，還遠遠達不到需要拼天賦的程度！

演算法這玩意在思路上從來不卡才是不正常。

首先你說遞歸有些理解不了，這個可能是分治發掌握不到位。遞歸常用的場景似乎就是分治法，你只要掌握了子問題如何劃分、原問題的解如何從子問題的解中導出就行了。

至於動態規劃，我個人認為這是分治法的一個改良。它的重點在於」打表格「，去看演算法是如何記錄最優子問題的解，如何避免大量重複計算。剩下問題和分治法幾乎完全一樣。

這些內容需要具體問題具體分析，我這隻能給你紙上談兵，具體示例只能去看課本之類的。

順道一說，你卡的這些內容早就超過了C++的範疇了，學習C++的經驗對理解這些東西估計沒啥幫助。題目中提到的C++似乎就已經干擾了回答者回答問題的思路。

先把演算法手工執行一遍，在腦子裡把思路理清了。

然後再去看程序代碼，C++代碼只是演算法用C++寫了一遍，實際執行的還是上一步的手工代碼。

個人建議，僅供參考。

你這不是學c++遇到困難，而是學演算法遇到困難了。

動態規劃和遞歸本質上都是兩點：

  1. 遞推關係
  2. 初始值

只是動態規劃把中間值都紀錄下來了，省去了很多重複計算。

至於你為什麼沒法理解遞歸，我猜測是因為你想每一步都順著遞歸推導下去，但人腦的棧很淺，你推兩步就棧溢出了。我的建議是不要模擬計算機來執行這段代碼，而是理解遞推關係。

例如一個青蛙跳台階，每次能往上跳1層或2層，問他至少需要跳幾次能跳到第10000層？

我們來用遞歸解決這個問題的話就是：

  1. 確定遞推關係。青蛙跳到第n層之前會在第n-1層或者是第n-2層，那麼我們只要知道跳到第n-1層或者第n-2層最少需要的步數，然後選這兩個值中的較小值，再加一，就是跳到第n層需要的步數。即f(n) = min(f(n-1), f(n-2)) + 1
  2. 確定初始值。只有遞推關係還不夠，還得要有初始值才能遞推得到一連串的數列，就像高中學的等差數列一樣，會告訴你首項、差值。確定初始值就等於確定首項。這個問題的初始值是f(1)=1, f(2)=1

但如果你以人腦模擬計算機來執行這一段，你會想跳到第10000層等於第9999層和第9998層步數的最小值加一，第9999層步數又等於……第9998層又等於…… 人腦容量根本做不到這種事情的。

至於動態規劃，就是把每一步算的值都存起來，既可以自底向上，也可以自上向下，你理解了遞歸再去理解動態規劃就容易了。

如果你同時對c++語法還不熟悉的話，那麼可能就更難理解遞歸，建議用python來學這些演算法，或者等你對c++一些基本概念更熟之後再來學演算法。

看不懂的代碼太多，敲出來按步 debug 吧，關注下核心的變數值的變化

推薦閱讀：
相关文章