Pasted

// Dynamic Programming
 
// Fibonacci
class Fibonacci {
 
public:
  int CalculateFibonacci(int n) {
    vector<int> fb(n+1);
    int i1 = 0, i2 = 1, i3 = 0;
    for (int i = 2; i <= n; i++) {
      i3 = i1 + i2;
      i1 = i2;
      i2 = i3;
    }
    return i3;
  }
};
 
 
// Given a stair with ‘n’ steps, implement a method to count how many possible ways are there to reach the top of the staircase, given that, at every step you can either take 1 step, 2 steps, or 3 steps.
 
public:
  int CountWays(int n) {
    int n1 = 1, n2 = 1, n3 = 2;
    int n4 = 0;
 
    for (int i = 3; i <= n; i++) {
      n4 = n1 + n2 + n3;
      n1 = n2;
      n2 = n3;
      n3 = n4;
    }
 
    return n4;
  }
};
 
// Given a number ‘n’, implement a method to count how many possible ways there are to express ‘n’ as the sum of 1, 3, or 4.
 
public:
  int CountWays(int n) {
    vector<int> dp(n+1);
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
 
    for (int i = 4; i <= n; i++) {
      dp[i] = dp[i-1] + dp[i-3] + dp[i-4];
    }
    return dp[n];
  }
};
 
 
// Given an array of positive numbers, where each element represents the max number of jumps that can be made forward from that element, write a program to find the minimum number of jumps needed to reach the end of the array (starting from the first element). If an element is 0, then we cannot move through that element.
 
Input = {2,1,1,1,4}
Output = 3
Explanation: Starting from index '0', we can reach the last index through: 0->2->3->4
 
class ArrayJump {
public:
  int countMinJumps(const vector<int> &jumps) {
    vector<int> dp(jumps.size(), numeric_limits<int>::max());
 
    dp[0] = 1;
 
    for (int start = 0; start < jumps.size(); start++) {
      for (int end = start + 1; end <= start + jumps[start] && end < jumps.size(); end++) {
        dp[end] = min(dp[end], dp[start] + 1);
      }
    }
    return dp[jumps.size() - 1];
  }
};
 
// Minimum jumps with fee
Given a staircase with ‘n’ steps and an array of ‘n’ numbers representing the fee that you have to pay if you take the step. Implement a method to calculate the minimum fee required to reach the top of the staircase (beyond the top-most step). At every step, you have an option to take either 1 step, 2 steps, or 3 steps. You should assume that you are standing at the first step.
 
Number of stairs (n) : 6
Fee: {1,2,5,2,1,2}
Output: 3
Explanation: Starting from index '0', we can reach the top through: 0->3->top
The total fee we have to pay will be (1+2).
 
int findMinFee(const vector<int> &fee) { 
    vector<int> dp(fee.size() + 1, numeric_limits<int>::max());
    dp[0] = 0;
 
    for (int start = 0; start <= fee.size(); start++) {
      for (int end = start + 1; end <= start + 3 && end <= fee.size(); end++) {
        dp[end] = min(dp[end], dp[start] + fee[start]);
      }
    }
    return dp[fee.size()];
  }
};
 
 
//Given a number array representing the wealth of n houses, determine the maximum amount of money the thief can steal without alerting the security system.
 
Input: {2, 5, 1, 3, 6, 2, 4}
Output: 15
Explanation: The thief should steal from houses 5 + 6 + 4
 
  int findMaxSteal(const vector<int> &wealth) { 
    vector<int> dp(wealth.size()+1);
    dp[0] = 0;
    dp[1] = wealth[0];
    // {2, 5, 1, 3, 6, 2, 4} -> // 2, 5, 5, 8, 11, 11, 15
    for (int i = 2; i <= wealth.size(); i++) {
      dp[i] = max(dp[i-1], dp[i-2] + wealth[i-1]);
      cout << dp[i] << "\t";
    }
    return dp[wealth.size()]; 
  }
};