家を略奪する(あなたは専門の泥棒で、街沿いの家を盗む計画です.各部屋には一定の現金が隠されています.あなたの窃盗に影響する唯一の制約要素は隣接する家に相互に連通する防犯システムが設置されています.もし2つの隣接する家が同じ夜に泥棒に侵入されたら、システムは自動的に警察に通報します.)...

例1:
入力:[1,2,3,1]出力:4解釈:1号室(金額=1)を盗み、3号室(金額=3)を盗む.盗まれた最高金額=1+3=4.
例2:入力:[2,7,9,3,1]出力:12解釈:1号家屋を盗む(金額=2)、3号家屋を盗む(金額=9)、次いで5号家屋を盗む(金額=1)窃盗した最高金額=1+3=4
に合格

/**
     * 
     * @param arr
     * @return
     *           ：      arr {2,7,9,3,1}，opt(i)         ，   opt(4)
     *   ，opt(4)：         4   ，     ，     4   ，
     *  opt(4) = opt(2) + arr[4],   opt(4) = opt(3) opt(4)         ，
     *  opt(4) = Math.max(opt(3),opt(2)+arr[4])
     *       ：(1)      0，return 0;
     *                 (2)      1，return arr[0];
     *            (3)  opt(2) = Math.max(opt(1),opt(0)+arr[2]),      
     *              2  ，return Math.max(arr[0],arr[1]);
     * 
     */

上記の解析に基づいて,再帰法と非再帰法を与えた.

　　　　//     

　　 public static int rob(int[] arr) {
        return rec_opt(arr,arr.length - 1);
    }
    
    public static int rec_opt(int[] arr,int i) {
        if(arr.length == 0) return 0;
        if(i == 0)
            return arr[i];
        else if(i == 1)
            return Math.max(arr[i-1], arr[i]);
        else {
            int A = rec_opt(arr,i - 2) + arr[i];
            int B = rec_opt(arr,i - 1);
            return Math.max(A, B);
            
        }
    }

//     
    public static int dp_opt(int[] arr) {
        if(arr.length == 0) {
            return 0;
        }
        if(arr.length == 1) {
            return arr[0];
        }
        if(arr.length == 2) {
            return Math.max(arr[0], arr[1]);
        }
        int[] opt = new int[arr.length];
        opt[0] = arr[0];
        opt[1] = Math.max(arr[1],arr[0]);
        for(int i = 2;i) {
            int A = opt[i - 2] + arr[i];
            int B = opt[i - 1];
            opt[i] = Math.max(A, B);
        }
        return opt[opt.length - 1];
    }

 
転載先:https://www.cnblogs.com/du001011/p/10472892.html