Giả sử Amal và Bimal đang chơi một trò chơi. Họ có một số mảng xác định n viên gạch có đánh số trên đó. Trong trò chơi này, người chơi có thể loại bỏ một, hai hoặc ba viên gạch từ trên cùng, và các số được đánh dấu trên các viên gạch bị loại bỏ sẽ được cộng vào điểm của người chơi đó. Nếu Amal luôn bắt đầu trước, chúng ta phải tìm xem Amal đạt được điểm an toàn tối đa là bao nhiêu.
Vì vậy, nếu đầu vào giống như nums =[1,2,3,4,5], thì đầu ra sẽ là 6 bởi vì, Amal có thể loại bỏ gạch {1}, {1,2} hoặc {1,2,3} , nếu Amal chọn hai hoặc ba phần tử đầu tiên, thì Bimal có thể lấy tất cả và nhận được điểm tối đa, nhưng nếu Amal chọn 1 lúc đầu, thì Bimal có thể lấy nhiều nhất {2,3,4} =9 và Amal có thể lấy 5, vì vậy tổng điểm của Amal là 1 + 5 =6.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau
- INF:=9999
- n:=kích thước của nums
- đảo ngược số lượng danh sách
- temp:=một mảng có kích thước n và điền bằng 0
- total:=một mảng có kích thước n và điền bằng 0
- đối với mỗi chỉ số i và giá trị val tính bằng num, thực hiện
- tổng [i]:=tổng [i-1] + val
- temp [0]:=nums [0]
- temp [1]:=temp [0] + nums [1]
- temp [2]:=temp [1] + nums [2]
- đối với tôi trong phạm vi từ 3 đến n - 1, thực hiện
- a:=nums [i]
- b:=nums [i] + nums [i-1]
- c:=nums [i] + nums [i-1] + nums [i-2]
- temp [i]:=tối đa a, b, c
- nhiệt độ trở lại [n-1]
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
INF = 99999 def solve(nums): n = len(nums) nums.reverse() temp = [0]*n total = [0]*n for i, val in enumerate(nums): total[i] = total[i-1] + val temp[0] = nums[0] temp[1] = temp[0]+nums[1] temp[2] = temp[1]+nums[2] for i in range(3, n): a = nums[i] b = nums[i] + nums[i-1] c = nums[i] + nums[i-1] + nums[i-2] temp[i] = max(a, b, c) return temp[n-1] nums = [1,2,3,4,5] print(solve(nums))
Đầu vào
[1,2,3,4,5]
Đầu ra
6