程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> (LeetCode OJ)House Robber【198】

(LeetCode OJ)House Robber【198】

編輯:關於C++

House Robber

My SubmissionsTotal Accepted: 45702 Total Submissions: 142460 Difficulty: Easy

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.

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.

Subscribe to see which companies asked this question

Hide Tags Dynamic Programming Show Similar Problems

動態規劃:

//理清思路:
//最值方案問題,考慮采用動態規劃  
//令maxV[i][0]表示第i個房子是獲取的最大值
//無論什麼時候最後一個人要麼是偷要麼不偷 
//如果最後一個是偷,顯然maxV[i] = maxV[i - 2]+nums[i]; 
//如果最後一個是不偷,maxV[i]=maxV[i-1];
class Solution {
public:
    int rob(vector& nums) {
        int n = nums.size();
        if(n == 0)
         {   
             return 0;
         }else if(n == 1)
         {   
            return nums[0];
         } 
          else
         {
            vector maxV(n, 0);
            maxV[0] = nums[0];
            maxV[1] = max(nums[0], nums[1]);
            for(int i = 2; i < n; i ++)
                maxV[i] = max(maxV[i-2]+nums[i], maxV[i-1]);
            return maxV[n-1];
        }
    }
};

或者想九度女生排座位那道題一樣:

class Solution {
public:
	int rob(vector& nums) {
		int  dp[10000][2];
		int sum = 0;
		dp[0][0] = nums[0];//偷
		dp[0][1] = 0;//不偷
		int i = 1;
		for (; i
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved