Number Of Ways To Earn Points - Leetcode Solution

Problem Description:

Given an integer n, and three arrays A, B, C of length n. A[i], B[i], C[i] represents the number of points you get if you sell the ith product on each of the three websites respectively. You can sell the ith product on one website or on several websites, but the total number of points you get for selling the ith product cannot exceed 100.

Return the maximum number of points you can get according to these rules.

Solution:

The problem can be solved using dynamic programming. We can define a 3-D array DP, where DP[i][j][k] represents the maximum number of points we can get from the first i products if we sell them on website A, B and C respectively and the total points from website A, B and C are j, k and i-j-k respectively.

The base case will be when i=0 and j=k=0. Since we have not sold any products, we have not earned any points.

For each new product i, we have three options. We can choose to sell the product on website A, B, or C. For each option, we can calculate the points earned from the ith product and add it to the points earned from the previous i-1 products.

For example, if we choose to sell the ith product on website A, the total points earned on website A would be DP[i-1][j-A[i]][k] + A[i], where j-A[i] is the remaining points that can be earned on website B and k is the points that can be earned on website C.

Similarly, if we choose to sell the ith product on website B or C, we can calculate the total points earned on that website and add it to the points earned from the previous i-1 products.

We can take the maximum value of DP[i][j][k] when i=n and 0<=j,k<=100 to get the maximum number of points we can earn.

The time complexity of the algorithm will be O(n100100), and the space complexity will be O(n100100) as we are using a 3-D array to store the results.

Code:

def max_points(A: List[int], B: List[int], C: List[int]) -> int:
    n = len(A)
    DP = [[[0 for _ in range(101)] for _ in range(101)] for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(0, 101):
            for k in range(0, 101):
                DP[i][j][k] = DP[i-1][j][k]
                if j>=A[i-1]:
                    DP[i][j][k] = max(DP[i][j][k], DP[i-1][j-A[i-1]][k] + A[i-1])
                if k>=B[i-1]:
                    DP[i][j][k] = max(DP[i][j][k], DP[i-1][j][k-B[i-1]] + B[i-1])
                if 100-j-k>=C[i-1]:
                    DP[i][j][k] = max(DP[i][j][k], DP[i-1][j][k] + C[i-1])
    return DP[n][100][100]

The code can be further optimized by using a 2-D array to store the results. Since the total points cannot exceed 100, we can use a 2-D array DP[j][k] to represent the maximum number of points we can get if we sell the first i products on website A, B and C respectively and the total points from website A and B are j and k respectively.

The time complexity of the optimized algorithm will be O(n100100), and the space complexity will be O(100*100) as we are using a 2-D array to store the results.

Code:

def max_points(A: List[int], B: List[int], C: List[int]) -> int:
    n = len(A)
    DP = [[0 for _ in range(101)] for _ in range(101)]
    for i in range(1, n+1):
        for j in range(100, -1, -1):
            for k in range(100, -1, -1):
                if j>=A[i-1]:
                    DP[j][k] = max(DP[j][k], DP[j-A[i-1]][k] + A[i-1])
                if k>=B[i-1]:
                    DP[j][k] = max(DP[j][k], DP[j][k-B[i-1]] + B[i-1])
                if 100-j-k>=C[i-1]:
                    DP[j][k] = max(DP[j][k], DP[j][k] + C[i-1])
    return DP[100][100]

1