Leetcode House robber

Question

私はHouse Robber問題（dp問題）をリートコードで試していました。 ユーザーGYXの1人からのこのソリューションは、シンプルでエレガントに見えます。

int rob(vector<int>& num) { 
    int n = num.size(); 
     if (n==0) return 0; 
     vector<int> result(n+1,0); 
     result[1] = num[0]; 
     for (int i=2;i<=n;i++){ 
      result[i] = max(result[i-1],result[i-2]+num[i-1]); 
     } 
     return result[n]; 
    } 

しかし、私は論理の周りに頭を浮かべることができませんでした。論理と、このような問題にどのようにアプローチするのかを教えてください。

Answer 1

k家の額をhouse[k]に保存するとします。

今や、私は、最初のk家屋（そして最初のkのみ）から略奪可能な金額の最大額をmax[k]に保存するとします。

は今何の家を検討していないので、max[0]=0

今、家の中で唯一の最初の家、max[1] =量を考慮し1

今考えると最初の2つの住宅、

max[2] = {どちらかmax[1]

は（我々が選んだの意味（私の現在の家の前に2ヵ所ある家が見つかるまで奪回した最大の金額）} = {max(max[1],house[2]+max[0])}

最初の3つの住宅同様同様に、max[3]=max(max[2],house[3]+max[1])

この傾向を見ると、max[k]=max(max[k-1],house[k]+max[k-2])が公式化されます。この値は、最後に家がなくなるまで計算されます。私たちは、最初のn家から奪回できる最大額を取得します。

DPの問題は、あなたが以前に慣れていたときにだけ頭を打ち、これは常に助けになります。

Answer 2

基本的に答えはf(n) = max(f(n-1), f(n-2) + arr[n])で、理由を尋ねています。

この配列arr = [9,1,7,9]とf(n)が関数であるとします。配列は唯一[9]とき

、あなたの最大f(0)はarr[0]になります。

配列が[9,1]ある場合は、あなたの最大f(1)がmax(arr[0], arr[1])です。

あなたが7を選択した場合、配列は、[9,1,7]である、あなたは1のでf(n-2) + arr[n]を選択しないすることができます。ただし、7を選択しないと、最大f(2)はf(1)と同じになります。これはf(n-1)です。配列は[9,1,7,9]のとき

、あなたは両方の1 & 7をドロップし、9、9 f(n) = max(f(n-1), f(n-2)+arr[n])方程式を満たす。このケースを選択する必要があります。