Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int getMinMoves(int stair, int &n, vector<int> &jumps, vector<int> &memo){
- if(stair == n){
- return 0;
- }
- if(memo[stair] != INT_MAX){
- return memo[stair];
- }
- int minMovesFromStair = INT_MAX;
- //make possible jumps from that stair
- for(int i = 1; i <= jumps[stair]; i++){
- if(stair + i <= n){
- // 1 added as we are jumping from current stair to stair + i
- minMovesFromStair = min(minMovesFromStair, 1 + getMinMoves(stair + i, n, jumps, memo));
- }
- }
- return memo[n] = minMovesFromStair;
- }
- int getMinMovesDP(int &n, vector<int> &jumps){
- //Storage & Meaning - The memo array as is, is the DP array
- // Meaning - dp[i] = Min moves from ith stair to nth stair
- vector<int> dp(n + 1, INT_MAX);
- //Direction - Smallest Problem at dp[n] - min moves to reach nth stair from nth stair = 0
- // Largest Problem at dp[0] - min moves to reach nth stair from 0th stair
- dp[n] = 0;
- // Travel & Solve - Travel from smallest subproblem to largest subproblem, by building up the solution'
- for(int i = n - 1; i >= 0; i--){
- for(int j = 1; j <= jumps[i]; j++){
- if(i + j <= n){
- dp[i] = min(dp[i], 1 + dp[i + j]);
- }
- }
- }
- //answer to largest problem
- return dp[0];
- }
- int main() {
- // your code goes here
- int n;
- cin >> n;
- vector<int> jumps(n);
- for(int i = 0; i < n; i++){
- cin >> jumps[i];
- }
- vector<int> memo(n + 1, INT_MAX);
- cout << getMinMoves(0, n, jumps, memo) << '\n';
- cout << getMinMovesDP(n, jumps) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
