https://www.youtube.com/watch?v=YBSt1jYwVfU&list=PLl0KD3g-oDOEbtmoKT5UWZ-0_JbyLnHPZ&index=2
When we are at some step, let's say here it doesn't matter how we got here. Maybe we took single steps. Maybe it was first two steps then one step. It doesn't matter because the problem doesn't tell us for example that two consecutive steps can be of size two something like that. It only matters where we are. This is why the state must be just a position i or pos like position and this suggests the dimension of DP should be that i position. Because the problem tells us to count ways, I will define that as integer, int dp[i], That means the number of ways to get here, if the problem asked me to compute the minimum number of jumps to make something, then that would be the minimum number of jumps. If the problem asked me "is it possible?" Then this would be just a boolean value that says whether I can get here (yes or no), i.e. true or false. If we need to maximize something that would be maximum value (that we need to maximize) to get here. If we define the state as int dp[i]; - the number of ways to get here, then we have an easy transition,because we know we can get to i from i-1 or i-2. Then the transition is dp[i]=dp[i-1] +dp[i-2]
Then when you're at some position i, you can't anymore say it doesn't matter how you got here. There are exponentially many ways you got here, but what is important is the number of jumps you made. There is a difference (if you are here), whether you made 1 jump or 2 or 3 jumps (maybe 0 if that's possible). This means we should add that as a dimension of dp. The state isn't just described as position, it's also the number of jumps to get here. Then I changed int dp[i] to int dp[i][k], that means the number of jumps to that position. At the end, instead of just printing dp[n] (i.e. the number of ways to get to the n of step), (we'll print the sum over) the answer would be Sdp[n][j] (j= number of jumps ) from j=0 to j=k, because we are allowed to make atmost K jumps, It's easy after that's defined to see their complexity as well. The space complexity is O(N*K) (given in the input, those are two dimensions). And every state you compute in constant time, dp[i][k] is dp[i-1][k-1] or dp[i-2][k-1], to that previous step where you made the number of jumps smaller by 1.