DP (1) - Count number of ways to cover a distance
Given a distance n, count total number of ways to cover the distance with 1, 2 and 3 steps. Input: n = 4 Output: 7 Explantion: Below are the four ways 1 step + 1 step + 1 step + 1 step 1 step + 2 step + 1 step 2 step + 1 step + 1 step 1 step + 1 step + 2 step 2 step + 2 step 3 step + 1 step 1 step + 3 step // C++ program to count number of ways in DP to cover a distance with 1, 2 and 3 steps #include<iostream> using namespace std; int main() { int n; std::cin>>n; int count[n+1]; // Initialize base values. There is one way to cover 0 and 1 // distances and two ways to cover 2 distance. count[0] = 1, count[1] = 1, count[2] = 2; // Fill the count array in from bottom to up manner for (int i=3; i<=n; i++) ...