ວິທີແກ້ໄຂບັນຫາລັກລອບໂຈນເຮືອນ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ Cisco Microsoft Oracle
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ຖະແຫຼງການບັນຫາ

ໃນບັນຫານີ້ມີເຮືອນຢູ່ຕາມຖະ ໜົນ ແລະໂຈນເຮືອນຕ້ອງໄດ້ລັກເຮືອນເຫຼົ່ານີ້. ແຕ່ບັນຫາກໍ່ຄືວ່າລາວບໍ່ສາມາດປຸ້ນເອົາເຮືອນໄດ້ຫຼາຍກວ່າ ໜຶ່ງ ຢ່າງຕໍ່ເນື່ອງເຊັ່ນ: ເຊິ່ງຢູ່ຕິດກັນ. ໃຫ້ບັນຊີລາຍຊື່ຂອງເລກເຕັມທີ່ບໍ່ແມ່ນລົບເຊິ່ງເປັນຕົວແທນ ຈຳ ນວນເງິນຂອງແຕ່ລະເຮືອນ, ພວກເຮົາຕ້ອງຊອກຫາ ຈຳ ນວນເງິນສູງສຸດທີ່ລາວສາມາດໄດ້ຮັບ.

ຍົກຕົວຢ່າງ

nums = [1,2,3,1]
4

ຄໍາອະທິບາຍ:ໂຈນເຮືອນ

ເຮືອນ Rob 1 (ເງິນ = 1) ແລະຫຼັງຈາກນັ້ນກໍ່ລັກເຮືອນ 3 (ເງິນ = 3).
ຈຳ ນວນເງິນທັງ ໝົດ ທີ່ທ່ານສາມາດລັກໄດ້ = 1 + 3 = 4.

nums = [2,7,9,3,1]
12

ຄໍາອະທິບາຍ:

ເຮືອນ Rob 1 (ເງິນ = 2), ເຮືອນ rob 3 (ເງິນ = 9) ແລະຫຼັງຈາກນັ້ນທີ 5 (ເງິນ = 1).
ຈຳ ນວນເງິນທັງ ໝົດ ທີ່ທ່ານສາມາດລັກໄດ້ = 2 + 9 + 1 = 12.

ວິທີການ

ປັນຫານີ້ບໍ່ສາມາດແກ້ໄຂໄດ້ໂດຍວິທີການໂລບມາກ.
ຂໍໃຫ້ເຮົາຍົກຕົວຢ່າງ:
nums = [1,7,9,5,1,3,4]

ຖ້າພວກເຮົາຈະໄປຫາສິ່ງທີ່ສູງສຸດໃນອາເລ (ເຊັ່ນ: 9), ພວກເຮົາຈະປ່ອຍຜົນບວກຂອງມັນໄວ້ (ຕົວຢ່າງ 7 + 5). ແລະດີທີ່ສຸດທີ່ພວກເຮົາສາມາດມີໄດ້ແມ່ນ 15 ເທົ່າກັບ ຈຳ ນວນທັງ ໝົດ.

ຖ້າພວກເຮົາໄປຊອກຫາອົງປະກອບ ຕຳ ແໜ່ງ ທີ່ຄັກຫລືຄີກພວກເຮົາມີເລກລວມ = 15 (7 + 5 + 3) ແລະຄູນບວກ = 15 (1 + 9 + 1 + 4).

ຄຳ ຕອບທີ່ດີທີ່ສຸດ ສຳ ລັບຕົວຢ່າງນີ້ແມ່ນ [7 + 5 + 4] = 12.

ສະນັ້ນເພື່ອແກ້ໄຂບັນຫາປະເພດນີ້ພວກເຮົາຕ້ອງໄດ້ຄົ້ນຫາທຸກທາງເລືອກຄືນ ໃໝ່ ແລະເລືອກເອົາສູງສຸດຈາກພວກມັນ. ຂໍໃຫ້ພວກເຮົາສະແດງວ່າ:

f (n) = ຈຳ ນວນເງິນທີ່ໃຫຍ່ທີ່ສຸດທີ່ທ່ານສາມາດລັກຈາກເຮືອນ ທຳ ອິດຈົນຮອດເຮືອນທີ່ຖືກດັດສະນີ.
Ai = ຈຳ ນວນເງິນທີ່ບ້ານດັດຊະນີ ith.

ຢູ່ແຕ່ລະເຮືອນພວກເຮົາມີທາງເລືອກທີ່ຈະລັກເອົາຫລືປະໄວ້.
ກໍລະນີ 1 - ຖ້າພວກເຮົາເອົາເຮືອນສຸດທ້າຍ:
ຫຼັງຈາກນັ້ນ, ພວກເຮົາບໍ່ສາມາດເລືອກເອົາເຮືອນ (n-1), ດັ່ງນັ້ນ f (n) = An + f (n-2)
ກໍລະນີທີ 2 - ຖ້າພວກເຮົາອອກຈາກເຮືອນສຸດທ້າຍ:
ຫຼັງຈາກນັ້ນ, ພວກເຮົາຈະຕິດກັບ ກຳ ໄລສູງສຸດຈົນຮອດເຮືອນ (n-1), ສະນັ້ນ f (n) = f (n-1)

ໃຫ້ພວກເຮົາເບິ່ງຄະດີພື້ນຖານ.
n = 0, f (0) = A0 ຢ່າງຈະແຈ້ງ.
n = 1, ຫຼັງຈາກນັ້ນ f (1) = ສູງສຸດ (A0, A1).

ດັ່ງນັ້ນພວກເຮົາສາມາດສະຫຼຸບສູດດັ່ງຕໍ່ໄປນີ້:
f (n) = ສູງສຸດ (An + f (n-2), f (n-1))

ນີ້ແມ່ນສູດສູດທີ່ພວກເຮົາສາມາດຈັດຕັ້ງປະຕິບັດໄດ້ໂດຍຜ່ານການເອີ້ນຄືນງ່າຍໆແຕ່ໃນທີ່ນີ້ຄວາມສັບສົນຂອງເວລາຈະເປັນ O (2 ^ n). ເພາະສະນັ້ນພວກເຮົາຈະໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ເຂົ້າຫາແລະເກັບຮັກສາຜົນໄດ້ຮັບລະດັບປານກາງໃນຂບວນ.
ຫຼັງຈາກການຄິດໄລ່ແລ້ວພວກເຮົາຈະສົ່ງຄືນມູນຄ່າທີ່ເກັບໄວ້ທີ່ດັດຊະນີ (ທີ່ສຸດ) ໃນແຖວ

ການປະຕິບັດ

ໂຄງການ C ++ ສຳ ລັບເຮືອນ Robber Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

int rob(vector<int>& nums)
{
    int n=nums.size();

    if(n==0) return 0;
    if(n==1) return nums[0];

    int a[n];

    a[0]=nums[0];
    a[1]=max(nums[0],nums[1]);

    for(int i=2;i<n;i++)
    a[i]=max(nums[i]+a[i-2], a[i-1]);

    return a[n-1];

}
int main() 
{
    vector<int> arr={1,2,3,1};
    
    cout<<rob(arr)<<endl;
    
  return 0; 
}
4

Java Program for House Robber Leetcode Solution

import java.util.*;
import java.lang.*;

class HouseRobber
{  
    public static int rob(int[] nums) {
        
        int n=nums.length;
        
        if(n==0) return 0;
        if(n==1) return nums[0];
        
        int a[]=new int[n];
       
        a[0]=nums[0];
        a[1]=Math.max(nums[0],nums[1]);
        
        for(int i=2;i<n;i++)
            a[i]=Math.max(nums[i]+a[i-2], a[i-1]);
        
        return a[n-1];
    }
    
    
    public static void main(String args[])
    {
        int arr[]={1,2,3,1};
        System.out.println(rob(arr));
    }
}
4

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການລັກລອບໂຈນເຮືອນ Leetcode

ຄວາມສັບສົນເວລາ

ໂອ (n): ພວກເຮົາ ກຳ ລັງຊັ່ງຊາຈາກເຮືອນທີ 1 ເຖິງເຮືອນທີ ໜຶ່ງ ໃນວົງມົນດຽວ, ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນເຮືອນທັງ ໝົດ.

ຄວາມສັບສົນໃນອະວະກາດ 

ໂອ (n): ພວກເຮົາໄດ້ໃຊ້ແຖວຂະ ໜາດ n ເພື່ອເກັບຜົນໄດ້ຮັບລະດັບກາງ.