House Robber——LeetCode

4607 단어 LeetCode
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
 
제목은 거리를 털려면 연속적인 두 집을 뺏으면 안 된다는 것이다. 그렇지 않으면 경찰에 신고할 것이다. 뺏거나 뛰어다니며 뺏을 수 있는 최대치를 출력할 수 밖에 없다.이것은 입문의 동칙 문제로 상한선이 없는 제한이 있는 01배낭 문제로 이해할 수 있다.
나의 사고방식은 다음과 같다.
수조 F[1...n]를 사용하여 제 i집에 강탈했을 때의 최대 이익은 F[i]라고 표시하면 제목에 따라 점차적인 공식 F[i]=max {F[i-1], F[i-2]+num[i]}를 쓸 수 있다. 그 중에서num[i]는 제 i집을 강탈하면 얼마의 이익을 얻을 수 있는지를 나타낸다.
다음은 귀속과 비귀속 두 가지 실현이다.
int[] max = new int[2000];



    public int rob(int[] num) {



        if (num == null || num.length == 0) {

            return 0;

        }

        if (num.length == 1) {

            return num[0];

        }

        if (num.length == 2) {

            return Math.max(num[0], num[1]);

        }

        Arrays.fill(max, -1);

        return choose(num.length - 1, num);

    }



    public int choose(int k, int[] num) {

        if (k == 0)

            return num[k];

        if (k < 0) {

            return 0;

        }

        if (max[k] == -1) {

            max[k] = Math.max(choose(k - 1, num), choose(k - 2, num) + num[k]);

        }

        return max[k];

    }

비귀속:
 public int rob2(int[] num) {



        if (num == null || num.length == 0) {

            return 0;

        }

        if (num.length == 1) {

            return num[0];

        }

        if(num.length==2){

            return Math.max(num[0],num[1]);

        }

        max[0]=num[0];

        max[1]=Math.max(num[0],num[1]);

        for(int i=2;i<num.length;i++)

        {

            max[i]=Math.max(max[i-1],max[i-2]+num[i]);

        }

        return max[num.length-1];

    }

좋은 웹페이지 즐겨찾기