The recurrence relation of recursion and tabulation are different

manoranjan · October 19, 2022, 1:35pm

The recurrence relation for recursion is: dp[i] = max( dp[i - 2] + wealth[i], dp[i - 1] )
And the recurrence relation for the tabulation is: dp[i] = max(dp[i-1], dp[i-2] + wealth[i-1])
Can someone clarify this?
Isn’t there a more straight-forward way to derive the tabulation from the recursion?

Course: Grokking Dynamic Programming Patterns for Coding Interviews - Learn Interactively
Lesson: House thief - Grokking Dynamic Programming Patterns for Coding Interviews

manoranjan · October 19, 2022, 3:40pm

It has to do with the indexes. Since we start from memo[0] = 0 and memo[1] = fees[0], we start the loop from i=1, so that we can access fees[1] and memo[i+1] = memo[2] and so on…

Consider ex: nums = [1,2,2,1]
Recurrence Relation: memo[i+1] = Math.max(memo[i], memo[i-1] + nums[i]);

houses & nums index (i)		0	1	2	3
nums		1	2	2	1
Houses	no house	1st house	2nd house	3rd house	4th house
dp	0 (dp[0] = 0)	1 (dp[1] = nums[0])	2 (dp[2] = max(nums[1] + dp[0], dp[1])) = max(2,1)	3 (dp[3] = max(nums[2] + dp[1], dp[2])) = max(3, 2)	3 (dp[4] = max(nums[3] + dp[2], dp[3])) = max(3, 3)
Dp index	0	1	2	3	4

Hence dp[4] = 3 is the answer

Course: Grokking Dynamic Programming Patterns for Coding Interviews - Learn Interactively
Lesson: House thief - Grokking Dynamic Programming Patterns for Coding Interviews