I am trying to learn dynamic programming, and for the most basic of problems like the staircase stepping I fully understand how to reach those objectie function/recurrence relationships. I had no idea how to apply DP to this problem and I thank you for taking the time to exlain it it in a table manner (non-recursive) because it truly captures the essence of dynamic programming that way, it feels like to me at least.
12.2 has been kicking my ass for 2 weeks now, I understand the purpose of pushing solutions to a map to reduce the amount of time spent processing solutions. People have tried to explain using a fib() function, which makes sense. Instinct tells me I should be running the original 12.1 to get solutions for each individual block, then multiplying out for the five. What throws me is how the combination works, there's an extra ? in the middle so the original solutions only make sense if every additional ? is a . I'm trying to understand dynamic programming and I keep getting "it's complicated, I won't go into it" 😂 I'm sat there like no, please do!
i did it with recursion (and memoisation for pt2). pseudocode with some details missing: if line[0] == '.': return ways(line[1..], targets) if line[0] == '#': targets[0] -= 1 return ways(line[1..], targets) if line[0] == '?': return ways('.' + line[1..], targets) + ways('#' + line[1..], targets)
Same, recursion and caching made it run in less than a second Took me a while to figure that out though, spent a lot of time trying to brute force part 2 the same as part 1 which was obviously never going to work in retrospect :D
I am trying to learn dynamic programming, and for the most basic of problems like the staircase stepping I fully understand how to reach those objectie function/recurrence relationships. I had no idea how to apply DP to this problem and I thank you for taking the time to exlain it it in a table manner (non-recursive) because it truly captures the essence of dynamic programming that way, it feels like to me at least.
12.2 has been kicking my ass for 2 weeks now, I understand the purpose of pushing solutions to a map to reduce the amount of time spent processing solutions. People have tried to explain using a fib() function, which makes sense. Instinct tells me I should be running the original 12.1 to get solutions for each individual block, then multiplying out for the five.
What throws me is how the combination works, there's an extra ? in the middle so the original solutions only make sense if every additional ? is a . I'm trying to understand dynamic programming and I keep getting "it's complicated, I won't go into it" 😂 I'm sat there like no, please do!
Awesome explanation! The way to handle dot counter and pound counter before checking is neat.
i did it with recursion (and memoisation for pt2). pseudocode with some details missing:
if line[0] == '.':
return ways(line[1..], targets)
if line[0] == '#':
targets[0] -= 1
return ways(line[1..], targets)
if line[0] == '?':
return ways('.' + line[1..], targets) + ways('#' + line[1..], targets)
interesting, thanks for sharing!
Same, recursion and caching made it run in less than a second
Took me a while to figure that out though, spent a lot of time trying to brute force part 2 the same as part 1 which was obviously never going to work in retrospect :D
Amazing, thanks for the tip. The "details missing" was a bit tricky
great explanation! how would you rate part 2's difficulty in codefoces?
hard to say, I'm no expert when it comes to judging difficulty 😅 but maybe problem D or so on a division 2 contest
when will you get married
Hi mom