看不懂就借鑒,不丟人,還省時(shí)間呢.

題目 : 你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你 不觸動(dòng)警報(bào)裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高

????????這道題剛開始也不太清晰,只知道可以套用動(dòng)態(tài)規(guī)劃,但具體的流程分析還不太熟練,所以還是看了解析.
????????看過之后理解的思路如下:

• 小偷偷竊時(shí)候不能連續(xù)偷。

• 小偷每家可有兩種狀態(tài),偷、不偷。

• 偷時(shí)，則前一家一定沒偷，即是前一家 沒偷總額+今天偷的金額

• 不偷時(shí)，則為前一家沒偷與偷的最大值。

如果每家金額為 moneys[]?, 則可設(shè)二維數(shù)組 values[Homes][]; 一維記偷與不偷的金額.則第 i 家金額總和為

?然后會(huì)發(fā)現(xiàn),數(shù)組中的數(shù)據(jù)都只使用了一次,所以,可定義兩個(gè)變量來存儲(chǔ),最后代碼如下:

代碼: