<p>You are given an integer array <code>rewardValues</code> of length <code>n</code>, representing the values of rewards.</p>

<p>Initially, your total reward <code>x</code> is 0, and all indices are <strong>unmarked</strong>. You are allowed to perform the following operation <strong>any</strong> number of times:</p>

<ul>
	<li>Choose an <strong>unmarked</strong> index <code>i</code> from the range <code>[0, n - 1]</code>.</li>
	<li>If <code>rewardValues[i]</code> is <strong>greater</strong> than your current total reward <code>x</code>, then add <code>rewardValues[i]</code> to <code>x</code> (i.e., <code>x = x + rewardValues[i]</code>), and <strong>mark</strong> the index <code>i</code>.</li>
</ul>

<p>Return an integer denoting the <strong>maximum </strong><em>total reward</em> you can collect by performing the operations optimally.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">rewardValues = [1,1,3,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<p>During the operations, we can choose to mark the indices 0 and 2 in order, and the total reward will be 4, which is the maximum.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">rewardValues = [1,6,4,3,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">11</span></p>

<p><strong>Explanation:</strong></p>

<p>Mark the indices 0, 2, and 1 in order. The total reward will then be 11, which is the maximum.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rewardValues.length &lt;= 2000</code></li>
	<li><code>1 &lt;= rewardValues[i] &lt;= 2000</code></li>
</ul>

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        # dp:
        # state transition:
        # Let dp[i][j] (true/false) be the state after the first i rewards, indicating whether we can get exactly j points.
        # The transition is given by: dp[i][j] = dp[i - 1][j − rewardValues[i]] if j − rewardValues[i] < rewardValues[i]
        dp = []
        rewardValues.sort()
        result = 0
        # we need to save all points possibilities, not just the max point
        # because greedy doesn't work
        for i, reward in enumerate(rewardValues):
            # initiate
            if i == 0:
                currDp = [False]*(reward+1)
                currDp[0] = True
                currDp[reward] = True
                result = reward
                dp.append(currDp)
                continue
            # consider taking reward
            currDp = [False]*(result+reward+1)
            for point in range(0, result+reward+1):
                # don't mark index i
                if len(dp[-1]) > point and dp[-1][point]:
                    currDp[point] = True
                #  or mark index i
                elif reward > point-reward and point-reward >= 0 and len(dp[-1]) > point-reward:
                    currDp[point] = dp[-1][point-reward]
                
                if currDp[point]:
                    result = max(result, point)
            dp.append(currDp)
        return result
                
            
        
        return result

# [1,1,3,3]
# dp = [[True, True], [True, True]]
# i = 0
# currDp = [True, True]
# i = 1
# currDp = [True, True]
# i = 2
# currDp = [True, True, False, True]
# point = 0 point = 1 point = 2, point = 3 3>3-3

110000