動态規劃之打家劫舍

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之内能夠偷竊到的最高金額。

示例 ：

輸入：[1,2,3,1]

輸出：4

解釋：偷竊 1 号房屋 (金額 = 1) ，然後偷竊 3 号房屋 (金額 = 3)。

偷竊到的最高金額 = 1 + 3 = 4 。

代碼：

public int rob(int[] nums)
{
     if(nums.length==0)
         return 0;
     if(nums.length==1)
    	 return nums[0];
     int []dp=new int[nums.length];
    	dp[0]=nums[0];
    	dp[1]=Math.max(nums[0], nums[1]);
     for(int i=2;i<nums.length;i++)
     {
    	dp[i]=Math.max(dp[i-2]+nums[i], dp[i-1]);
     }
    return dp[nums.length-1];
}