[プログラマー]窃盗

[プログラマー]窃盗
コードテスト練習-窃盗
すべての家は丸く配置されている.
どの家にも隣接する家と防犯装置がつながっている→隣接する2つの家を強奪する→警報が鳴る.
家ごとにお金を並べてあげると、泥棒が盗むことができるお金の最高価格を返すことができる解決関数を書きます.
問題を理解する
つまり、警報が鳴らない限り、できるだけ多くのお金を出すべきだということです.

つまり、連続する2軒は選べません.→i 1軒目は選べない→i+1.

また重要なのは、円形です.→最初の家を選んだら、最後の家は選べない.そこでfirstという変数をparameterごとに渡します.

、つまり、最初の家を選んだかどうかを共有すべきだと思います.

i→i+2の選択から考えるべきです.もちろんi+2を選ばなくてもいいですi+3は非常に大きな数かもしれないので」このような展開があれば、動的計画法だと思います.

問題をやりましょう
エラー1
firstには、最初の要素を選択するかどうかの情報が含まれています.
選択

現在:recur(i+2,first)

選択

現在x:recur(i+1,first)

lenが家の数だと思ってください.最後の家に着いた場合はfirstを選択するかどうかによって異なります.

if(n==len&!first)→この場合、n番目の要素の選択も許可され、

if(n==len&&first)→この場合は0を返す必要があります.要素の選択が許可されていないためです.

dp[i]は[i.end]の最長値に格納される.
エラー→dpを2 D(上から下へ)に変更→テスト精度成功、効率運転時エラー
最初のセットを選択すると、最初に戻ります.dp値が設定されている場合、最初の値が選択されていない場合(より大きな値が表示される場合)、値は更新されません.
だからdpを2次元→dpに変更[i][first]

import java.util.*;
class Solution {
    public int len;
    public int[][] dp = new int[1000000][2];
    public int[] gmoney;
    public int solution(int[] money) {
        int answer = 0;
        gmoney = money;
        len = money.length;
        for(int i=0;i<len;i++)Arrays.fill(dp[i],-1);
        // 첫 번째 집을 선택 O 경우, 첫번째집을 선택 X 경우
        dp[0][1] = recur(2,1) + money[0];
        dp[0][0] = recur(1,0);
        
        answer = Math.max(dp[0][1],dp[0][0]);

            
        return answer;
    }
    public int recur(int n, int first){
        System.out.println("n :"+n+", first :"+first);
        // 선택할 수 없는 경우
        if(n==len-1 && first == 1)return 0; // 첫번째 집을 선택했었음 && n 이 마지막 집
        if(n >= len) return 0; // out of range
        // solved problem
        if(dp[n][first]!=-1)return dp[n][first];
        // n 번째 집을 선택하지 않는 경우, 선택하는 경우
        dp[n][first] = Math.max(recur(n+1,first),recur(n+2,first)+gmoney[n]);
        // System.out.println("n :"+n+", first :"+first+" --> 최대값 : "+dp[n]);
        return dp[n][first];
    }
    
}

成功:上へ
上のペーストはO(n)ですが、おそらくO(2 n)くらいです.
いずれにしてもO(n)でも効率的には失敗している.再帰関数が呼び出されたからですか?再帰的に解くときっと時間がかかるけど….この問題は最初から私にそんな方法で解決させないのですか.どうしてこんなことになったのか...誰かが教えてくれることを願っています.
for文をプールに変えましょう
現在私の場合は再帰関数nでlen-1→ここから再帰的に戻るのでdp[i]=Mathとなります.max(dp[i+1],dp[i+2]+mony[i])を行っています.(i...最後の最低価格)
しかしそうはしない、dp[i]=Math.max(dp[i-1],dp[i-2]+mony[i])は任意の数でもよいが,これはゼロである...iの最大値に含まれます.

そして、ここでは、最初の家は選択の状況と選択のない状況を分けて開放しなければならない.

import java.util.*;
class Solution {
    public int len;
    public int[][] dp = new int[1000000][2];
    public int[] gmoney;
    public int solution(int[] money) {
        int answer = 0;
        int i = 0;
        gmoney = money;
        len = money.length;
        for(i=0;i<len;i++)Arrays.fill(dp[i],-1);
        // dp[i][0] = Math.max(dp[i-1][0],dp[i-2][0]+money[i])
        dp[0][0] = 0; // 첫번째 집은 선택 x
        dp[1][0] = money[1]; // 첫번째 집을 선택 x , i가 1일 때 최댓값 
        dp[0][1] = money[0]; // 첫번째 집을 선택 o
        dp[1][1] = dp[0][1]; // 첫번째 집을 선택 o, i가 1일 때 최댓값
        // 문제조건이 집은 3개이상이라고 주어짐
        for(i=2;i<len-1;i++){
            dp[i][0] = Math.max(dp[i-2][0]+money[i] , dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-2][1]+money[i] , dp[i-1][1]);
        }
        // i == n-1 일 때는, 첫 번째 집은 선택하지 않은 경우에 대해서만 업데이트 
        dp[i][0] = Math.max(dp[i-2][0]+money[i],dp[i-1][0]);
        dp[i][1] = Math.max(dp[i-2][1],dp[i-1][1]);
        answer = Math.max(dp[i][0],dp[i][1]);
        
            
        return answer;
    }

    
}