python-乘积最大

解题思路:

递归搜索。

假设字符串长度为n，下标从0开始。则我们可以在第0~n-2位数后面放”ד号。

接下来遍历所有符合条件的位置，每个位置有两种情况，放和不放。

求出所有符合条件的结果，即可求出答案。

具体求解过程可参考下面代码，有详细注释。

注意事项:

参考代码:

def dfs(T,now):      #T中记录乘号的位置，now为遍历到s中的第几个数  
    global n,m,s,ans  
  
    if len(T) == m:  #如果T中已经标记了m个乘号位置  
        num = 1      #存放乘积  
        t = 0  
        for item in T:   #求乘积  
            num = num * int(s[t:item+1])  
            t = item+1  
        num = num * int(s[t:])  #不要忘记最后一个要乘的数  
        if num > ans:  
            ans = num  
        return  
  
    if now >= n-1:  
        return  
  
    dfs(T+[now],now+1)   #在第now位数后面放乘号  
    dfs(T,now+1)         #不在第now位数后面放乘号  
  
  
if __name__ == '__main__':  
    n,m = map(int,input().strip().split())  
    s = input().strip()  
    ans = 0    #存放最终答案  
    dfs([],0)    
    print(ans)