看网上说安卓社招地狱难度啊
1 1

相关推荐

10-03 22:20
算法工程师
pdd算法题题目:未来N天,多多君想好了要吃的汉堡,且已知第天,的汉堡价格为Pi,吃掉汉堡后可以获得,与价格同等数量的汉堡积分。每100个汉堡积分会,自动兑换成一张免单券,可以免费吃任意汉堡,免单券的有效期为3天,且使用免单券吃掉的汉堡不能获得汉堡积分。找到一个最省钱的吃汉堡计划同学问我此题如何写,我们都不会尝试了半天后,写了回溯和动态规划两种方式,不知道是不是能通过所有案例,试了一些发现是对的,不知道哪里需要修改代码如下:```def dfs(nums, path, ans, curMon, start):    if start == len(nums):        if sum(path) > ans[0]:            ans[0] = sum(path)        return    if curMon >= 100:        curMon -= 100        for i in range(3):            if start+i < len(nums):                path.append(nums[start+i])                dfs(nums, path, ans, curMon, start+i+1)                path.pop()                curMon += nums[start+i]    else:        curMon += nums[start]        dfs(nums, path, ans, curMon, start+1)def min_cost_to_eat_hamburgers(N, prices):    MAX = sum(prices)    dp = [[MAX] * (MAX + 1) for _ in range(N+1)]   # dp[i][j]表示第i天结束时,积分为j的最小花费    dp[0][0] = 0  # 第0天,0积分的花费为0    for i in range(1, N+1):        price = prices[i-1]        for j in range(1, MAX+1):            # 不使用免单券的情况            if j >= price:                dp[i][j] = min(dp[i][j], dp[i-1][j-price] + price)            # 使用免单券的情况            if j >= 100:                if i+1 < N+1:dp[i+1][j-100] = min(dp[i+1][j-100], dp[i][j])                if i+2 < N+1:dp[i+2][j-100+prices[i]] = min(dp[i+2][j-100+prices[i]], dp[i][j]+prices[i])                # if i+3 < N+1:dp[i+2][j-100+prices[i]] = min(0, 1)                if i+3 < N+1 and j-100+prices[i]+prices[i+1] <=MAX:dp[i+3][j-100+prices[i]+prices[i+1]] = min(dp[i+3][j-100+prices[i]+prices[i+1]], dp[i][j]+prices[i]+prices[i+1])           return min(dp[-1])nums = [70, 60, 20, 80, 50, 30, 40, 70]ans = [0]dfs(nums, [], ans, 0, 0)print(sum(nums)-ans[0])print(min_cost_to_eat_hamburgers(len(nums), nums))
投递拼多多集团-PDD等公司10个岗位
点赞 评论 收藏
分享
牛客网
牛客企业服务