這真是一道好題!這道題不僅考察了抽象思維,還考察了分析能力、化繁為簡的能力,同時還有對基本功的考察。想順利地做出這道題還挺不容易!我倒在了第一步與第二步:抽象思維和化繁為簡。題目的要求稍微復雜一些,我就看不出問題的本質了。這一方面體現的是抽象能力的缺失,另一方面體現的則是拙劣的思考能力。
1. 題目
2. 思考
這道題給我的啟示就是:多多動腦,理解題意,抽象化分析題目,然后化繁為簡,用大腦的思考量去簡化代碼。本質上,這是一道動態規劃題,但是找到動態規劃之前,還需要兩步預處理。
- 第一步:得計算出每個數值對應的和具體是多少,把這個和寫到一個數組中,這樣就可以避免處理原數組中相同的數;
- 第二步:如何破解題意信息?題目中說到如果選了值為i的數,那么就不能再選值為
i-1
,也不能選i+1
的數了。我原本的處理方式是使用兩個數組,分別記錄從左到右和從右到左的最大值,最后把兩個方向上的值合在一起得到最終的結果。但是這么做實在太繞了!
那有沒有簡單的方法呢?1, 2, 3, 4, ..., i-1, i, i+1, ...
對于這么一串數字,在判斷數值i
時能得到的最大點數,其實就是相當于從dp[i-1]
和 dp[i-2]
中遞推;有同學可能會問,題目中不是說dp[i]也依賴于dp[i+1]取不取嗎?如果dp[i+1]取了,那么dp[i]就不能取了。雖然是這么個理兒,但是dp[i+1]的問題就留給(i+1)-1來避免。 這樣就保證了對數i+1決策的時候,是對數i進行判斷了的。
上面這一段的邏輯很重要,非常重要。以至于它決定了你能否很快的解出題來。
3. 代碼
本次只做分析,代碼略過,日后補上。