題目： 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. 題目大意： 你是一名專業強盜，計劃沿著一條街打劫。每間房屋都儲存有一定金額的錢，唯一能阻止你打劫的約束條件就是房屋之間有安全系統相連，如果同一個晚上有兩間相鄰的房屋被闖入，它們就會自動聯絡警察，因此不可以打劫相鄰的房屋。 重點內容給定一列非整，代表每間房屋的金額，算出在不驚動警察的前提下一晚上最多可以打劫到的金錢數。 解題思路：動態規劃（Dynamic Programming） 用狀態轉移方程：sum[i] += Math.max(sum[i-2], sum[i-3]); 第i個位置的最大值由max（sum[i-2], sum[i-3]）決定， 把最大值轉移給sum[i] 算法源碼：
public class Main { public static void main(String[] args){ int[] sum= {1,9,10,10,7}; System.out.println(robber(sum)); } public static int robber(int[] sum){ if (sum== null || sum.length == 0) { return 0; } //如果只有一個元素，返回這個元素值 if(sum.length==1){ return sum[0]; } else if(sum.length==2){ //如果有兩個元素，返回其中較大的值 return Math.max(sum[0], sum[1]); }else if(sum.length==3){ //如果有三個元素，比較第一個元素和第三個元素之和與第二個元素的值，返回較大者 return Math.max(sum[0]+sum[2], sum[1]); } //把第一個和第三個元素的和賦給第三個元素，以便以后比較 if (sum.length > 3) { sum[2] += sum[0]; } //從第四個元素開始處理就需要用到公式了,也是從第四個開始重新賦值,元素少于四的時候，公式不成立 int i = 3; for(;i<sum.length;i++){ sum[i] += Math.max(sum[i-2], sum[i-3]); } //舉個例子:如有4個元素，i=3，執行一次循環之后(這個時候i=4):最后一個元素=最后一個元素+前兩個中較大的； return Math.max(sum[i-1], sum[i-2]);//再比較最后一個和倒數第二個 }}博客園鏈接：HouseRobber(java)
新聞熱點
疑難解答
