打家劫舍

发表于 | 分类于 ， ， |

打家劫舍I II III

198.打家劫舍 I

198

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        //有相应的测试样例才需要，没有不用也行
        if(n==0) return 0;
        if(n==1) return nums[0];
        
        //dp[i]表示长度为i的数组，最多能偷取多少钱
        vector<int> dp(n);

        //base case
        dp[0]=nums[0];
        dp[1]=max(nums[0], nums[1]);

        for(int i=2;i<n;i++){
            //对于每家可以选择偷或者不偷
            dp[i]=max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func rob(nums []int) int {
    n := len(nums)
    //有相应的测试样例才需要，没有不用也行
    if n == 0 {
        return 0
    }
    if n == 1 {
        return nums[0]
    }
    
    //dp[i]表示长度为i的数组，最多能偷取多少钱
    dp := make([]int, n)
    
    //base case
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i := 2; i < n; i++ {
        //对于每家可以选择偷或者不偷
        dp[i] = max(dp[i-2]+nums[i], dp[i-1])
    }
    return dp[n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
213.打家劫舍 II

213

213_1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        
        if(n==0) return 0;
        if(n==1) return nums[0];

        return max(helper(nums, 0, n-2), helper(nums, 1, n-1));
    }
    int helper(vector<int>& nums, int start, int end){
        int n=nums.size();

        //dp[i]表示长度为i的数组，最多能偷取多少钱
        vector<int> dp(n);

        //base case
        if(start==0){
            dp[0]=nums[0];
            dp[1]=max(nums[0], nums[1]);
        }
        if(start==1){
            dp[0]=0;
            dp[1]=nums[1];
        }

        for(int i=2;i<=end;i++){
            //对于每家可以选择偷或者不偷
            dp[i]=max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[end];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func rob(nums []int) int {
    n := len(nums)
    
    if n == 0 {
        return 0
    }
    if n == 1 {
        return nums[0]
    }
    
    return max(helper(nums, 0, n-2), helper(nums, 1, n-1))
}

func helper(nums []int, start, end int) int {
    n := len(nums)
    
    //dp[i]表示长度为i的数组，最多能偷取多少钱
    dp := make([]int, n)
    
    //base case
    if start == 0 {
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
    }
    if start == 1 {
        dp[0] = 0
        dp[1] = nums[1]
    }
    
    for i := 2; i <= end; i++ {
        //对于每家可以选择偷或者不偷
        dp[i] = max(dp[i-2]+nums[i], dp[i-1])
    }
    return dp[end]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
337.打家劫舍 III

337

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> res = helper(root);
        return max(res[0], res[1]);
    }

    // 长度为2的数组，0：不偷，1：偷
    vector<int> helper(TreeNode* root) {
        if (root == nullptr){
            return {0, 0};
        }

        vector<int> left = helper(root->left);
        vector<int> right = helper(root->right);

        // 偷当前节点，字节点不偷
        int res1 = root->val + left[0] + right[0];

        // 不偷当前节点，字节点可偷可不偷，取决于收益大小
        int res2 = max(left[0], left[1]) + max(right[0], right[1]);

        return {res2, res1};  //注意顺序，res2在前，res1在后，因为是后序遍历
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func rob(root *TreeNode) int {
    res := helper(root)
    return max(res[0], res[1])
}

// 长度为2的数组，0：不偷，1：偷
func helper(root *TreeNode) []int {
    if root == nil {
        return []int{0, 0}
    }
    
    left := helper(root.Left)
    right := helper(root.Right)
    
    // 偷当前节点，字节点不偷
    res1 := root.Val + left[0] + right[0]
    
    // 不偷当前节点，字节点可偷可不偷，取决于收益大小
    res2 := max(left[0], left[1]) + max(right[0], right[1])
    
    return []int{res2, res1} //注意顺序，res2在前，res1在后，因为是后序遍历
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
-------------本文结束 感谢阅读-------------
0%