2016年(2)
分类: C/C++
2016-07-04 15:31:16
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.
题意为给定一个数组,从数组中取出元素相加(不能连续取两个相邻的元素)能够得到的最大值
设P[k]为k个元素的数组能得出的最大值;
设M[k]为数组中索引为k - 1的元素值(索引值从0开始计数);
则有以下DP方程:
P[0] = 0;
P[1]=M(1);
P[k]=max(M(k) + P(k - 2), P(k-1)); (由于不能取相邻的元素,M(k) + P(k-2)表示取第k - 1个元素的值,P(k-1)表示不取第k - 1个元素的值)
则函数为:
点击(此处)折叠或打开