Facing issue Dry run issue

#1

What i am understood by dry run is-
dp[i] will have 1 for sure if it non zero number
Now if (i-1)*10+i<=26 then add 1 to dp[i]
else
dp[i]=dp[i-1]

But when i dry ran for 25114
2->1
25->2
251->2
2511->3
25114->5
Where am i missing any case?

#2

See you got the intuition, just have to correct it’s implementation

  • If you ith correct is valid that is s[i] is [1,…26] then we will make it as valid integer.
  • So what we are doing is that if we are at ith position, we will check is it valid s[i] or not.
  • If its valid then we will do dp(i-1) + some side case too.(which you are missing)
  • Now what this side case is, that we will check if our s[i-1]*10 + s[i] is valid or not. Now we have two cases, that it can be valid or it is not. If its not then no need to do any thing.

But if its then what we will do is make,

dp(i-1) + some side case too.(which you are missing)

dp[i] = dp[i-1] + dp(i-2)(case you were missing) lets understand this with example.

  • Let input be: 25114
    Here , we first check for 2 that is dp[1]. Its a valid s[i] character so.
    Dp[1] = 1

  • Now, we check for 5 that is dp[2], Its a valid s[i] character so. And also s[i-1]*10 + s[i] is also valid which is (s[i-1]*10 + s[i] = 25), so
    Dp[2] = dp[1] + dp[0] => 2

  • Now, we check for 1 that is dp[3], Its a valid s[i] character so. But you will see that s[i-1]*10 + s[i] is not valid which is (s[i-1]*10 + s[i] = 51), so
    Dp[3]= dp[2] => 2

  • Now, we check for 1 that is dp[4], Its a valid s[i] character so. And also s[i-1]*10 + s[i] is also valid which is (s[i-1]*10 + s[i] = 11), so
    Dp[4]= dp[3]+ dp[2]=> 4

  • Now, we check for 4 that is dp[5], Its a valid s[i] character so. And also s[i-1]*10 + s[i] is also valid which is (s[i-1]*10 + s[i] = 14),so
    Dp[5]= dp[4]+ dp[3] => 6

Hope this will clear your doubt, if not feel free to ask. And if your doubt is solved, then please mark it as resolved.

1 Like
#3

oh so is it like if it is less than 26 then it means no change in previous count?

#4

It’s like if current element is less then 26 and current element + 10* previous element is valid(less then 26) we make
dp[i] = dp[i-1] + dp(i-2)
But if only current element is less then 26 then
dp[i] = dp[i-1]

#5

But why dp[i-1]+dp[i-2} :scream:

#6

In this input, see this case

here we are at s[i] that is 5, makes a valid point
let’s check for 25 as previous element is 2, yes it also makes a valid point cause it’s less then 26. So when it makes a valid point, i also have to maintain count by contribution of 25 na? So that’s why i did
Dp[i] = dp[i-1] + dp[i-2] or in naive way see it like this
dp[5] = dp[“2”](contribution of 5) + dp[“25”](as contribution of all elements which were valid till 5)

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.