# How does one generate the dimensions of a dynamic programming problem?

I'm doing this problem https://leetcode.com/problems/maximum-alternating-subsequence-sum/ and attempting to change my code to use a matrix/array. I'm unable to figure out what the dimensions are. Drawing it out hasn't made it clear for me either and I think I'm missing a core concept or the recurrence relation. As far as I know, we either take an element or don't and when we do, we need to check whether we need to add it or subtract it.

I know the number of subsequences we can possibly have is 2^m where m = length of the sequence. So at worst the matrix is of size 2^m. But how can one accurately calculate the dimensions of the matrix here?

class Solution:
def maxAlternatingSum(self, nums: List[int]) -> int:
perms = []
def dp(add, i, tmp):
if i == len(nums):
perms.append(tmp[:])
return 0

res = nums[i]
taken = 0
not_taken = 0

tmp.append(nums[i])
taken = res + dp(False, i + 1, tmp)
tmp.pop()
not_taken = dp(True, i + 1, tmp)
else:
tmp.append(res*-1)
taken = (res * -1) + dp(True, i + 1, tmp)
tmp.pop()
not_taken = dp(False, i + 1, tmp)

res = max(taken, not_taken)
return res
ans = dp(True, 0, [])
print(perms, len(perms)) # num of subsequences is 2^length
return ans
$$$$
`
• Coding questions are off-topic. Any question that requires us to read your code is likely off-topic here. Please replace the code with concise pseudocode (which doesn't require us to know any particular programming language and doesn't require us to read 20 lines of code).
– D.W.
Dec 29 '21 at 23:33
• Also, it is not clear to me what you are asking. Please make sure the question is self-contained, so we don't have to click on a link to understand what you're asking. (Also we want the question to remain useful even if the link stops working.) It's not clear how you plan to use a matrix or array so I'm not sure whether we're going to be able to tell you what dimensions to make it.
– D.W.
Dec 29 '21 at 23:34