Ladder Problem using Dynamic Programming (Bottom-up Approach) in O(n)

[amiable143]

In the given problem we have to find the no. of ways in which we can reach the top of ladder from the bottom, where

n = total number of steps in ladder.
k = maximum numbers of steps that can be taken at a time.

I tried solving it in O(n) using bottom up approach ,but recurrence relation fails when n <= k.Below is my code. I watched some solution ,they just manually calculate dp[n] for n <= k. How it can be more efficient as it became O(n*k) when i calculated it in line 5-10.

  #include <iostream>
int Tot_Ways(int n, int k, int *dp)
{    
       dp[0] = 1;
       for(int i = 1;i <= k;i++){ /// line 5-10 for solving the dp[n] for n <= k in O(n*k)
            dp[i] = 0;
            for(int j = 1;j <= k;j++){
                 if (i-j >= 0)
                 dp[i] = dp[i] + dp[i-j];}
               }  /// line 10
       for(int i = k+1;i <= n;i++){  /// solved for n > k using recurrence relation dp[n+1] = dp[n] - dp[n-k] in O(n)
            dp[i] =2*dp[i-1] - dp[i-1-k];
             }
 return dp[n];}

int main(){
     int n , k;
     std:: cin >> n >> k;
     int dp[1000];
     for(int i=0; i<1000; i++){
         dp[i] = -1; }
     std:: cout << Tot_Ways(n ,k ,dp);
 }

[dhayden]

For the first k steps, dp[i] is the sum of the steps before it. Just keep that running sum in a variable. This will eliminate the loop from lines 7-10.

[amiable143]

@dhayden sir, are u telling me to manually give the value of dp[n] until n= k ??
i failed to understand what u r saying ? plz explain

[dhayden]

This is the partial solution for steps 0 through k-1. This might now be quite right though. Is the goal to reach the last rung in the latter, or to step off the last rung onto the roof? If the goal is to reach the top rung that there is 1 way from the last rung and 1 way from the second to last rung, and then it gets interesting.

    // dp[0] is the top step. dp[n-1] is the bottom step
    dp[0] = 1;

    // At step 1 you can jump to the top, or go to step 0 and
    // then take however many options there are from step 0.

    // At step 2, you can jump to the top, or jump to step 1 or jump
    // to step 0.

    // The process continues. At each step, you can jump to the top, or
    // jump to any of the steps above you and take however many steps
    // there are from there.  So just keep track of the total number of
    // ways to get to the top from any of the steps above you.
    unsigned sumFromStepsAbove = dp[0];
    for (int step = 1; step < k; step++) {
        dp[step] = 1 + sumFromStepsAbove;
        sumFromStepsAbove += dp[step];
    }