Count number of ways to cover a distance - GeeksforGeeks

Count number of ways to cover a distance - GeeksforGeeks

Count number of ways to cover a distance Given a distance 'dist, count total number of ways to cover the distance with 1, 2 and 3 steps. Examples: Input: n = 3 Output: 4 Below are the four ways 1 step + 1 step + 1 step 1 step + 2 step 2 step + 1 step 3 step Input: n = 4 Output: 7 We strongly recommend you to minimize your browser and try this yourself first. // A naive recursive C++ program to count number of ways to cover // a distance with 1, 2 and 3 steps #include using namespace std; // Returns count of ways to cover 'dist' int printCountRec(int dist) { // Base cases if (dist<0) return 0; if (dist==0) return 1; // Recur for all previous 3 and add the results return printCountRec(dist-1) + printCountRec(dist-2) + printCountRec(dist-3); } // driver program int main() { int dist = 4; cout << printCountRec(dist); return 0; } Output: 7 The time complexity of above solution is exponential, a close upper bound is O(3n). If we draw the complete recursion tree,

Read full article from Count number of ways to cover a distance - GeeksforGeeks