如果我們添加新的約束，我們如何解決著名的盜屋者問題：盜賊總共最多可以搶劫 k 所房子？
問題描述：你是一名職業劫匪，計劃搶劫街道上的房屋。每棟房子都藏有一定數量的錢，唯一阻止你搶劫它們的唯一限制是相鄰的房子都有安全系統，如果同一天晚上有兩個相鄰的房子被闖入，它會自動聯系警察。
給定一個整數陣列 nums 代表每個房子的錢數，回傳你今晚可以在不驚動警察的情況下搶劫的最大金額。
示例 1：
輸入：nums = [1,2,3,1] 輸出：4 解釋：搶房子 1（錢 = 1），然后搶房子 3（錢 = 3）。您可以搶劫的總金額 = 1 3 = 4。
uj5u.com熱心網友回復：
原始問題可以通過遵循遞回公式使用動態規劃解決：
D(i) = max{ D(i-2) value[i] , D(i-1) }
^ ^
rob house i don't rob house i
通過為您可以搶劫的最大房屋數量添加額外的維度，您可以輕松修改解決方案：
D(i, k) = max { D(i-2, k-1) value[i], D(i-1, k) }
當然，當需要添加一個停止子句時 k < 0
然而，額外的維度會將時間復雜度增加 1 倍k。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344357.html
上一篇：分析Leetcode問題“974.可被K整除的子陣列和”的時間復雜度
下一篇：有條件的3個嵌套回圈的時間復雜度