Mountain Scenes | Dynamic Programming

Walkthrough of the Mountain Scenes dynamic programming problem that featured in the 2016 NAIPC programming competition.
Mountain Scenes problem:
open.kattis.com/problems/scenes
Source Code:
github.com/williamfiset/Algor...
Algorithms code repository:
github.com/williamfiset/algor...
Video slides:
github.com/williamfiset/algor...
Website:
www.williamfiset.com
Audio intro/outro composed by Richard Saney ([e-mail])
0:00 Intro
0:35 Mountain scenes problem statement
2:20 Problem hints
3:00 Problem analysis
3:38 Counting the total number of scenes
9:08 Counting plain scenes
11:00 Psuedocode

[@amanthapliyal2636]

Great Explanation of the concept!
Was able to understand both Recursive way and then why we could use DP!

[@satyajitdas2780]

Thanks. William. Perfect explanation. Looking for more DP problems.

[@piyushnaithani7689]

Awesome, after a long time I see a nice DP problem solver on youtube

[@mzmzgreen]

Awesome explanation! Could you please analyze the time/space complexity of the algorithms you're showing?

[@ramkrishnakulkarni8289]

100th like. Absolutely loved the video. Waiting for more videos on dp.

[@mgehad]

Hey Thank you for your efforts.
May I ask you.
- is it possible to mod the plain scenes count then subtract the total from the plain or its gonna cause errors?

[@bazgo-od7yj]

8:23 why does it say 11, not10?

[@afzalsiddique7165]

12:42 -> Why "ribbon < 0"? And not "ribbon

[@rahulsangvikar7973]

Because ribbon = 0 is fine. We can skip the current column completely. But we can't add negative ribbon to the column

[@CrystalSergeant]

next time please provide bottom up approach is it is harder to get.

[@giorgos-4515]

13:08 thats a dp technique called memoization there is a great video from codecamporg that illustrates it perfectly

[@lenlen8099]

To me dp comes from memoization

[@giorgos-4515]

@@lenlen8099 i mean dp is mostly recursion and recursion can get costly so it makes sense,just not entirely.(if it was any kind of joke it went completely over my head)