今天看了1個華為西安研究院的1個女生代碼大神的總結(jié)很有感悟，下面這句話送給大家：
只有好的程序員才能寫出人類可以理解的代碼
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.
the objective function is basically:
dp(i) = max(dp[i⑵] + num[i], dp[i⑴]),
this means the current max is the max of the position i⑵ plus the current num[i], or the max of the previous one i⑴ (cannot including num[i] with i⑴ position, otherwise it will trigger the alarm)
我的解決方案：
class Solution {
public:
int rob(vector<int>& nums)
{
if(nums.empty())return 0;
int length = nums.size();
vector<int> dp(length,0);
dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
for(int i =2; i< length; ++i)
{
dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[length-1];
}
};c語言解決方案：
#define max(a, b) ((a)>(b)?(a):(b))
int rob(int num[], int n) {
int a = 0;
int b = 0;
for (int i=0; i<n; i++)
{
if (i%2==0)
{
a = max(a+num[i], b);
}
else
{
b = max(a, b+num[i]);
}
}
return max(a, b);
}
python解決方案：
class Solution:
# @param num, a list of integer
# @return an integer
def rob(self, num):
# DP O(n) time, O(1) space
# ik: max include house k
# ek: max exclude house k, (Note: ek is also the maximum for house 1,...,k⑴)
# i[k+1]: num[k] + ek #can't include house k
# e[k+1]: max(ik, ek) # can either include house k or exclude house k
i, e = 0, 0
for n in num: #from k⑴ to k
i, e = n+e, max(i,e)
return max(i,e)
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
