educative.io

2 questions about the solution in the Examples section

Courses
,
#1

Link: Dynamic Programming: Introduction - Grokking Coding Interview Patterns in Go

In 1 of 2:

  • why the formula can solve the problem? How you get the formula?
  • how the table is generated, what is every column and row for? Is the row index or the column?
#2

Hi @Wenjie_Liu

  1. The formula is derived from the concept of subproblems and optimal substructure. We also consider two cases while solving this problem i.e., excluding the element from given array to make a sub-array and including the element. So, dp[index-1][sum] shows that the current element is not included, whereas dp[index-1][sum-num[index]] shows that element is included in the subarray.

  2. The table is created to store the solutions to the subproblems. The row of the table represents the index of the array(nums) and the column represents the sum(total) of the subarray ending at that index.

I hope it helped.