educative.io

Issue in debugging

Courses
,
#1

func rob(nums []int) int {

if len(nums) == 1 {

    return nums[0]

}

dp:=make(map[int]int,len(nums)+1)

var robme func(nums []int, cur int) int

robme = func(nums []int, cur int) int {

    if cur >= len(nums) {

        return 0

    }

if val,ok:= dp[cur];ok{

    return val

}

    max1 := nums[cur] + robme(nums, cur+2)

    max2 := robme(nums, cur+1)

    dp[cur] = max(max1, max2)

   

    return dp[cur]

}

// Rob the first house to the second-to-last house

max1 := robme(nums[:len(nums)-1], 0)

// Rob the second house to the last house

max2 := robme(nums[1:], 0)

fmt.Println("%v",dp)

// Return the maximum of the two cases

return max(max1, max2)

}

func max(a, b int) int {

if a > b {

    return a

}

return b

}
I first implement iterartive approch (remove dp map references ) which works fine expect large test set.
then added dp map to hadle the large test set. It fails for [1,2,3] cant point exact issue. Please help
PS: I intend on working with recursion and memoization only

#2

Hello @Ashish_Karki,

Can you please share the lesson link as well? Thanks.

#3

The approach i used is slightly different; just wanted to know what i am doing is wrong

1 Like
#4

Hi @Ashish_Karki,

I’ve looked at the code you shared and it seems to me that the issue with the provided code is related to how it calculates the maximum amount that can be robbed. The code should be designed to handle a circular list of houses, where you can either rob the first house or the last house but not both.

Let’s dry run the test case [1, 2, 3] on the code:

  1. The code starts by considering two cases:

    • Robbing from the first house to the second-to-last house: [1, 2]
    • Robbing from the second house to the last house: [2, 3]

  2. The code uses dynamic programming to calculate the maximum amount that can be robbed in both cases. It recursively considers whether to rob the current house and move two houses ahead or to skip the current house and move one house ahead.

For the first case [1, 2]:

  • Robbing house 1: 1 + robme([3], 2) = 1
  • Skipping house 1: robme([2], 1) = 2
  • The maximum between these two is 2.

For the second case [2, 3]:

  • Robbing house 2: 2 + robme([], 2) = 2
  • Skipping house 2: robme([3], 1) = 3
  • The maximum between these two is 3.
  1. Finally, it returns the maximum of the two cases, which is max(2, 3) = 3.

The issue here is that it doesn’t consider the circular nature of the problem. In this case, you can rob the first and last houses together because they are not adjacent. So, the correct answer for [1, 2, 3] should be 1 + 3 = 4.

To fix this issue, you need to modify the code to consider the circular aspect of the problem and ensure that it correctly calculates the maximum amount that can be robbed in a circular manner. You will need to add additional checks and iterate over the previous maximum value while calculating sum and the current maximum value, by updating this code you’ll be able to judge which value to consider while calculating the maximum amount of money you can rob.

Please let me know if this helps you in debugging your code. Feel free to share any more suggestions and feedbacks.

Happy learning!