checkio上一道python题目求助

776667

原题目是这样的：
Stair Steps

There is a staircase with N steps and two platforms; one at the beginning of the stairs and the other at the end. On each step a number is written (ranging from -100 to 100 with the exception of 0.) Zeros are written on both platforms. You start going up the stairs from the first platform, to reach the top on the second one. You can move either to the next step or to the next step plus one. You must find the best path to maximize the sum of numbers on the stairs on your way up and return the final sum.

                         __
                   __   /  |
         ______   /  | | _____
        /      | |  _____|  0
   __  /      _____|  2
  /  ||  _____| -1
|  _____| -3
____|  5
  0  
Input: Numbers on stairs as a tuple of integers.

Output: The final sum for the best path as an integer.

Example:

golf((5, -3, -1, 2)) == 6
golf((5, 6, -10, -7, 4)) == 8
golf((-11, 69, 77, -51, 23, 67, 35, 27, -25, 95)) == 393
golf((-21, -23, -69, -67, 1, 41, 97, 49, 27)) == 125
Precondition:

0 < |steps| ≤ 10

&#8704; x ∈ steps: -100 < x < 100

你需要编写一个函数golf(numbers)来解决这个爬楼梯游戏，参数numbers是一个元组，元组中每个值依次代表每层阶梯的值，每次行动你可以选择往上爬1层或2层阶梯，目的是求出爬到顶层时经过阶梯值之和的最大值。需要注意的是起点和终点的值都是0，也就是说numbers代表的是起点和终点之间的阶梯的值，比如numbers = (5,-3,1,2)在函数中要当作(0,5,-3,1,2,0)。
我本来以为按照正值必踩，负值选大的踩就能解决问题，于是就这么写了：

1. def golf(numbers):
   
2.     numbers = [0] + list(numbers) + [0]
   
3.     result = 0
   
4.     i = 0
   
5.     while i < len(numbers)-1:
   
6.         if numbers[i+1]>=0:
   
7.             result += numbers[i+1]
   
8.             i += 1
   
9.         elif numbers[i+1]<0 and numbers[i+2]>=0:
   
10.             result += numbers[i+2]
    
11.             i += 2
    
12.         elif numbers[i+1]<0 and numbers[i+2]<0:
    
13.             if numbers[i+1] > numbers[i+2]:
    
14.                 result += numbers[i+1]
    
15.                 i += 1
    
16.             else:
    
17.                 result += numbers[i+2]
    
18.                 i += 2
    
19.     return result

复制代码

然而在golf((-21, -23, -69, -67, 1, 41, 97, 49, 27))中行不通，用这种解法会比正确答案多踩上一个-21。
思考了一阵没想出解法，桑心啊，想请教下这题应该怎么解才对

SixPy

SixPy 发表于 2016-9-20 20:37
这其实是个组合问题
一步有 3 种走法
后一步与前一步相关联

用 numpy 的 数组运算 来写个简单的例子吧~

• from numpy import array as nparr, arange as nparng
• def golf(nums):
•     if len(nums)%2: nums = list(nums)+[0]
•     n = [(a, b, a+b) for a,b in zip(nums[::2], nums[1::2])]
•     s = nparr([0]*3)
•     for i in range(len(n)):
•         s = (s + nparr(n[ i ])).reshape(-1, 1)
•         if i==1: s = s[nparng(s.size) != 1, :]
•     return s.max()
• data = ((-21, -23, -69, -67, 1, 41, 97, 49, 27)
•        ,(-11, 69, 77, -51, 23, 67, 35, 27, -25, 95)
•        ,(5, 6, -10, -7, 4)
•        ,(5, -3, -1, 2))
• for nums in data:
•     print(golf(nums), '\t', nums)
  

结果：

125        (-21, -23, -69, -67, 1, 41, 97, 49, 27)
393        (-11, 69, 77, -51, 23, 67, 35, 27, -25, 95)
8          (5, 6, -10, -7, 4)
6          (5, -3, -1, 2)

happy_ltq

木有太看懂

SixPy

这其实是个组合问题
一步有 3 种走法
后一步与前一步相关联
所以每两步有 3 x 3  = 9 种走法
在9个组合中找到 总和 最大的那一组。
以此类推~

APocri

动态规划?

SixPy

SixPy 发表于 2016-9-21 10:05
用 numpy 的 数组运算 来写个简单的例子吧~

优化算法，提高速度~

1. from numpy import array as nparr, arange as nparng
   
2. 
   
3. def golf(nums):
   
4.     if len(nums)%2: nums = list(nums)+[0]
   
5.     n = (nparr((a, b, a+b)) for a,b in zip(nums[::2], nums[1::2]))
   
6.     s = (next(n).reshape(-1,1) + next(n)).flatten()[nparng(9)!=1].max()
   
7.     for x in n: s = (s + x).max()
   
8.     return s #.max()        
   
9. 
   
10. data = ((-21, -23, -69, -67, 1, 41, 97, 49, 27)
    
11.        ,(-11, 69, 77, -51, 23, 67, 35, 27, -25, 95)
    
12.        ,(5, 6, -10, -7, 4)
    
13.        ,(5, -3, -1, 2))
    
14. 
    
15. for nums in data:
    
16.     print(golf(nums), '\t', nums)

复制代码

Damn_it

完全没看懂