leetcode198：打家劫舍

题目链接

leetcode

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    状态表示：
        f[i] 表示前 i 个房屋能取到的最高总金额
    状态计算：
        根据最后一个点进行划分。
        不选第 i 点，问题转化为从 1 ~ i-1 取得的最高金额
            f[i] = max(f[i], f[i - 1])
        选择第 i 个点，因为不能选择相邻的点，所以前面只能从 1 ~ i-2 中选
            f[i] = max(f[i], f[i - 2] + nums[i])
    边界条件：
        f[0] = nums[0]
        f[1] = max(f[0], nums[1])
    最终答案：f[n−1]

    时间复杂度：O(n)
        其中 n 是数组长度，只需要对数组遍历一次。
    空间复杂度：O(n)
*/
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];

        vector<int>f (n, 0);
        // base case
        f[0] = nums[0];
        f[1] = max(nums[0], nums[1]);
        for (int i = 2; i < n; i ++) {
            f[i] = max(f[i - 1], f[i - 2] + nums[i]);
        }

        return f[n - 1];
    }
};

/*
    优化空间

    时间复杂度：O(n)
        其中 n 是数组长度，只需要对数组遍历一次。
    空间复杂度：O(1)
        只存储前两个房屋的最高总金额，而不需要存储整个数组的结果。
*/
class Solution_3 {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];

        int last2 = nums[0], last1 = max(nums[0], nums[1]);
        for (int i = 2; i < n; i ++) {
            int temp = last1;
            last1 = max(last1, last2 + nums[i]);
            last2 = temp;
        }

        return last1;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> test_cases = {
        {1, 2, 3, 1},
        {2, 7, 9, 3, 1}
    };

    for (auto& nums : test_cases) {
        cout << "Input: ";
        for (int num : nums) {
            cout << num << " ";
        }
        cout << endl;
        cout << "Output: " << solution.rob(nums) << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   动态规划：
       使用两个变量 prev1 和 prev2 分别表示前一个状态和前两个状态的最大金额。
       对于每个房屋，有两种选择：
           偷窃当前房屋：current = nums[i] + prev2
           不偷窃当前房屋：current = prev1
       更新 prev1 和 prev2，选择两种情况中的最大值。
   边界条件：
       如果数组为空，返回 0。
       如果数组只有一个元素，返回该元素的值。

   时间复杂度：O(n)
       遍历一次数组，时间复杂度为 O(n)。
   空间复杂度：O(1)
       使用了两个变量 prev1 和 prev2，空间复杂度为 O(1)。
*/
// rob 计算在不触动警报的情况下，能够偷窃到的最高金额
func rob(nums []int) int {
    n := len(nums)
	if n == 0 {
		return 0
	}
	if n == 1 {
		return nums[0]
	}

	prev1, prev2 := nums[0], 0
	for i := 1; i < n; i++ {
		current := max(prev1, nums[i] + prev2)
		prev2 = prev1
		prev1 = current
	}

	return prev1
}

func main() {
	// 测试用例
	testCases := []struct {
		nums    []int
		expected int
	}{
		{
			nums:    []int{1, 2, 3, 1},
			expected: 4,
		},
		{
			nums:    []int{2, 7, 9, 3, 1},
			expected: 12,
		},
	}

	for i, tc := range testCases {
		result := rob(tc.nums)
		fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}