动态规划实例--数组不连续取数问题（python实现）问题：
给定⼀个长度为N的⼀维数组
举例：输⼊：[1,3,5,2,1,9,4,3,7]
取数规则：不允许取连续的两个数。
求：这个数组在给定规则下取到数字的最⼤和是？
本例中，答案为：1+5+9+7=22
解题思路
新建⼀个与输⼊数组input_num⼤⼩相同的数组max_num
记max_num[i]为前i+1天的最⼤训练天数(因为数组第⼀项是max_num[0])
max_num[0]=input_num[0]
max_num[1]=max(input_num[0],input_num[1])
当i>1,
max_nums[i]= max(max_nums[i-1],max_nums[i-2]+input_num[i])
从头到尾遍历计算max_nums，则最终max_nums中的最后⼀项即为所求
代码实现（python 2.7）
input_raw=raw_input('please enter the array(array):\n').split()
input_array= [int(i) for i in input_raw]
global max_num
max_num=[0for i in range(len(input_array))]
max_num[0]=input_array[0]
max_num[1]=max(input_array[0],input_array[1])
global array
array=input_array
python获取数组长度def max_train_time(i):
if i<2:
pass
else:
max_num[i]= max(max_num[i-1],max_num[i-2]+array[i])
for i in range(2,len(array)):
max_train_time(i)
print'The max training time is:\n',max_num[-1]
程序实例测试
此处假设输⼊数组长度不⼩于3，否则此问题⽆意义
#instance1
please enter the array(array): 131
The max training time is:
3
#instance2
please enter the array(array): 254
The max training time is:
6
#instance3
please enter the array(array): 135219
The max training time is:
15
#instance4
please enter the array(array): 135219437
The max training time is:
22

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。