C語言打家劫舍問題怎么解決

本篇內容介紹了“C語言打家劫舍問題怎么解決”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

原題

你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都圍成一圈，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。

示例 1:

輸入: [2,3,2]
輸出: 3
解釋: 你不能先偷竊 1 號房屋（金額 = 2），然后偷竊 3 號房屋（金額 = 2）, 因為他們是相鄰的。

示例 2:

輸入: [1,2,3,1]
輸出: 4
解釋: 你可以先偷竊 1 號房屋（金額 = 1），然后偷竊 3 號房屋（金額 = 3）。
     偷竊到的最高金額 = 1 + 3 = 4 。

解題

這道題的變化是，同樣是一個數組，但是首尾相連了，也就是成了一個環，那么原本遞推的方式也就行不通了，因為任何一個節點其實地位都相等了，也就找不到最初的狀態，無法進行遞推了。

但我們可以將現在的問題轉化成我們已經解決的問題，仔細想想。所謂的首尾相連，針對狀態進行劃分，可以有三種情況：

1. 首尾節點都不選擇

2. 只選擇首節點，不選擇尾結點

3. 只選擇尾結點，不選擇首節點

因為我們最終是要求出最大值，那么只需要考慮后面兩種情況，而這樣的話，又可以轉化成了原本的線性數組了。

接下來讓我們看看代碼：

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        if (nums.length == 1) {
            return nums[0];
        }

        // 因為收尾相連，無法按照最初的動態規劃來做，因為沒有一個可以開始的點。
        // 那么就將未知問題轉化為已知問題，針對首尾兩個節點，可以有三種情況：
        // 1、首尾節點都不選擇
        // 2、只選擇首節點，不選擇尾結點
        // 3、只選擇尾結點，不選擇首節點
        // 因為是要取最大值，且是非負整數數據，所以只考慮后兩種情況

        return Math.max(
            // 只選擇首節點，不選擇尾結點
            calMax(nums, 0, nums.length - 2),
            // 只選擇尾結點，不選擇首節點
            calMax(nums, 1, nums.length - 1)
        );
    }

    public int calMax(int[] nums, int start, int end) {
        // 存儲當前位置，下一個位置，和再下一個位置的結果
        int current = 0;
        int next_1 = 0;
        int next_2 = 0;
        // 動態規劃，利用中間結果，尋找最大值
        for (int i = end; i >= start; i--) {
            current = Math.max(
                // 當前不偷
                next_1,
                // 當前偷
                nums[i] + next_2
            );
            next_2 = next_1;
            next_1 = current;
        }
        return current;
    }
}

“C語言打家劫舍問題怎么解決”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！