python-拿糖果

解题思路:

动态规划，建立一个数组dp[n]，dp数组中的每一个值初始化为0。其中dp[i]表示当前糖果为i时，小明最多能拿多少个糖果。

①建立一个函数每次筛选符合条件的p值，也就是<=sqrt(m)的m的质因数。程序中给这个函数命名为T。

②更新dp[1 to n],具体如下：

   for m in range(1,n+1):  
       primes = T(m)  
 
       for p in primes:  
           if m - 2*p >= 0:  
               dp[m] = max(dp[m],p+dp[m-2*p])

③输出dp[n]即可。

注意事项:

参考代码:

from math import sqrt  
  
def Isprime(x):  
    if x == 0 or x == 1:  
        return False  
      
    for i in range(2,int(sqrt(x))+1):  
        if x % i == 0:  
            return False  
    return True  
  
def T(x):               #挑选p值，参数x为当前所剩余的糖果数，也就是问题中的m
    cho = []  
    x_sqrt = sqrt(x)  
    for i in range(2,int(x_sqrt)+1):  
        if x % i == 0 and Isprime(i):  
            cho.append(i)   
  
    return cho  
  
def f(n):  
      
    dp = [0 for i in range(n+1)]  
  
    for m in range(1,n+1):  
        primes = T(m)  
  
        for p in primes:  
            if m - 2*p >= 0:  
                dp[m] = max(dp[m],p+dp[m-2*p])  
  
    print(dp[n])  
      
  
if __name__ == '__main__':  
    n = int(input().strip())  
    f(n)