Giả sử chúng ta có một số n, chúng ta phải tìm hai hoặc nhiều số sao cho tổng của chúng bằng n, và tích của các số này được tối đa hóa, chúng ta phải tìm tích đó.
Ví dụ, nếu đầu vào là n = 12, thì đầu ra sẽ là 81, vì 3 + 3 + 3 + 3 = 12 và 3 * 3 * 3 * 3 = 81.
Để giải quyết, chúng ta thực hiện các bước sau:
- Định nghĩa hàm dp(). Hàm này nhận n
- nếu n bằng 0, trả về 1
- ans := 0
- với i trong khoảng 1 đến n + 1:
- ans := max(ans, i * dp(n - i))
- trả về ans
- Từ phương thức chính: trả về dp(n)
Lưu ý: Đây là phương pháp đệ quy đơn giản (chưa tối ưu). Thực tế, để tối đa hóa tích với tổng cố định, nên chia thành nhiều số 3 nhất có thể (và 2 nếu dư 1).
Ví dụ
class Solution:
def solve(self, n):
def dp(n):
if n == 0:
return 1
ans = 0
for i in range(1, n + 1):
ans = max(ans, i * dp(n - i))
return ans
return dp(n)
ob1 = Solution()
print(ob1.solve(12))
Input
12
Output
81