Given K buildings with N floors and a person standing on the ground who can make at most M jumps. The person has to climb to the top and collect maximum points. Find the maximum number of points that can be collected if the person can either climb up the stairs to the next floor of the same building or he can jump to the next floor of any of the adjacent buildings.
Example:
Input: N = 5, M = 2, K = 3,
points = [ [4, 5, 1, 2, 10],
[9, 7, 3, 20, 16],
[ 6, 12, 13, 9, 8] ]
Output: 70
Explanation: Start from building 2. Collect the 9 points in the first floor.
Jump to building 3. Collect the 12 points from the second and 13 points from third floor. (Jump 1)
Jump back to building 2. Collect the 20 points from fourth floor and 16 points in fifth floor. (Jump 2)
Number of jumps made = 2
Number of points collected= 9+12+13+20+16 = 70 pointsInput: N = 4, M = 1, K = 3,
points = [ [7, 5, 4, 10],
[8, 9, 20, 16],
[ 12, 13, 3, 8] ]
Output: 61
Approach: Given problem can be solved using dynamic programming:
- First we define the state of dp
- dp(i, j, k) state – the maximum number of points that can be collected if the person is at ith floor having made at most j jumps and ended up at kth building
- Then we will define the base cases
- If there is only one floor then the person cannot jump, put the number of points at that location.
- If there are 0 jumps allowed then can choose one of the three building and keep climbing up on the same building.
- so, person can only take points from prev floor of same building and add current points
- Then we will define the transition between states
- if we are on first building then we can:
- come from the first building, one floor down, no jumps
- come from the next building, one floor down, one jump added
- add points stored in building 1 at ith floor for both cases
- If we are on intermediate building then we can:
- come from the previous building, one floor down, one jump added
- come from the current building, one floor down, no jump
- can come from the next building, one floor down, one jump added
- will add points stored in intermediate building at ith floor for all 3 cases
- If we are on last building then we can:
- come from previous building, one floor down, one jump added
- come from last building, one floor down, no jump added
- will add points stored in last building at ith floor for both cases
- For the final answer, return the maximum of points collected over the top floor of all building after engaging in permissible number of jumps.
Below is the implementation of the above approach:
C++14
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;int solve(vector<vector<int> >& a, int floors, int jumps, int buildings){ /* dp(i, j, k) represents state of the maximum number of points that can be collected if the person is at ith floor having made at most j jumps and ended up at kth building. */ int dp[floors + 1][jumps + 1][buildings + 1]; // Initializing dp with 0 memset(dp, 0, sizeof(dp)); for (int i = 1; i <= floors; i++) { for (int j = 0; j <= jumps; j++) { for (int k = 0; k < buildings; k++) { // Base case: first floor if (i == 1) { // Cannot jump on ground floor // from any other building dp[i][j][k] = a[k][i - 1]; } // Base case: no jumps allowed else if (j == 0) { /* can choose one of the buildings and keep climbing up on the same building so can only take points from prev floor of same building and add current points */ dp[i][j][k] = dp[i - 1][j][k] + a[k][i - 1]; } // transition else { // first building if (k == 0) { /* 1)can come from building 1, one floor down, no jumps. 2)can come from building 2, one floor down, one jump added. add points stored in building 1 at the ith floor for both cases. */ dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][k + 1]) + a[k][i - 1]; } // Last Building else if (k == buildings - 1) { /* 1)Can come from building k-1 from one floor below, one jump added. 2)Can come from building k from one floor below, no jump added. add points stored in building k at the ith floor for both cases. */ dp[i][j][k] = max( dp[i - 1][j - 1][k - 1], dp[i - 1][j][k]) + a[k][i - 1]; } // intermediate buildings else { /* 1)Can come from the building k-1, one floor down, one jump added 2)Can come from the building k, one floor down, no jump 3)Can come from the building k+1, one floor down, one jump added. add points stored in building k at the ith floor for all 3 cases */ dp[i][j][k] = max( { dp[i - 1][j - 1][k - 1], dp[i - 1][j][k], dp[i - 1][j - 1][k + 1] }) + a[k][i - 1]; } } } } } // Return the maximum of points collected // over the top floor of all building after // engaging in permissible number of jumps int ans = 0; for (int building = 0; building < buildings; building++) ans = max(ans, dp[floors][jumps][building]); return ans;}// Driver codeint main(){ // Number of floors // and number of jumps allowed. int N = 5, M = 2, K = 3; // Number of points // at each floor of the buildings. vector<vector<int> > a = { { 4, 5, 1, 2, 10 }, { 9, 7, 3, 20, 16 }, { 6, 12, 13, 9, 8 } }; // Function call cout << solve(a, N, M, K) << endl; return 0;} |
Java
// Java implementation for the above approachimport java.util.*;class GFG{ static int solve(int[][] a, int floors, int jumps, int buildings) { /* dp(i, j, k) represents state of the maximum number of points that can be collected if the person is at ith floor having made at most j jumps and ended up at kth building. */ int [][][]dp = new int[floors + 1][jumps + 1][buildings + 1]; for (int i = 1; i <= floors; i++) { for (int j = 0; j <= jumps; j++) { for (int k = 0; k < buildings; k++) { // Base case: first floor if (i == 1) { // Cannot jump on ground floor // from any other building dp[i][j][k] = a[k][i - 1]; } // Base case: no jumps allowed else if (j == 0) { /* can choose one of the buildings and keep climbing up on the same building so can only take points from prev floor of same building and add current points */ dp[i][j][k] = dp[i - 1][j][k] + a[k][i - 1]; } // transition else { // first building if (k == 0) { /* 1)can come from building 1, one floor down, no jumps. 2)can come from building 2, one floor down, one jump added. add points stored in building 1 at the ith floor for both cases. */ dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - 1][k + 1]) + a[k][i - 1]; } // Last Building else if (k == buildings - 1) { /* 1)Can come from building k-1 from one floor below, one jump added. 2)Can come from building k from one floor below, no jump added. add points stored in building k at the ith floor for both cases. */ dp[i][j][k] = Math.max( dp[i - 1][j - 1][k - 1], dp[i - 1][j][k]) + a[k][i - 1]; } // intermediate buildings else { /* 1)Can come from the building k-1, one floor down, one jump added 2)Can come from the building k, one floor down, no jump 3)Can come from the building k+1, one floor down, one jump added. add points stored in building k at the ith floor for all 3 cases */ dp[i][j][k] = Math.max( Math.max( dp[i - 1][j - 1][k - 1], dp[i - 1][j][k]), dp[i - 1][j - 1][k + 1] ) + a[k][i - 1]; } } } } } // Return the maximum of points collected // over the top floor of all building after // engaging in permissible number of jumps int ans = 0; for (int building = 0; building < buildings; building++) ans = Math.max(ans, dp[floors][jumps][building]); return ans; } // Driver code public static void main(String[] args) { // Number of floors // and number of jumps allowed. int N = 5, M = 2, K = 3; // Number of points // at each floor of the buildings. int[][] a = { { 4, 5, 1, 2, 10 }, { 9, 7, 3, 20, 16 }, { 6, 12, 13, 9, 8 } }; // Function call System.out.print(solve(a, N, M, K) +"\n"); }}// This code is contributed by Princi Singh |
Python3
# Python 3 implementation for the above approachdef solve(a, floors, jumps, buildings): #dp(i, j, k) represents state of the maximum #number of points that can be collected if #the person is at ith floor having made at #most j jumps and ended up at kth building. dp = [[[0 for i in range(buildings + 1)] for j in range(jumps + 1)] for k in range(floors + 1)] for i in range(1, floors + 1, 1): for j in range(0, jumps + 1, 1): for k in range(buildings): # Base case: first floor if (i == 1): # Cannot jump on ground floor # from any other building dp[i][j][k] = a[k][i - 1] # Base case: no jumps allowed elif(j == 0): # can choose one of the buildings # and keep climbing up on the # same building so can only take # points from prev floor of same # building and add current points dp[i][j][k] = dp[i - 1][j][k] + a[k][i - 1] # transition else: # first building if (k == 0): # 1)can come from building 1, # one floor down, no jumps. # 2)can come from building 2, # one floor down, one jump added. # add points stored in building 1 # at the ith floor for both cases. dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][k + 1]) + a[k][i - 1] # Last Building elif(k == buildings - 1): # 1)Can come from building k-1 from # one floor below, one jump added. # 2)Can come from building k from # one floor below, no jump added. # add points stored in building k # at the ith floor for both cases. dp[i][j][k] = max(dp[i - 1][j - 1][k - 1],dp[i - 1][j][k]) + a[k][i - 1] # intermediate buildings else: # 1)Can come from the building k-1, # one floor down, one jump added # 2)Can come from the building k, # one floor down, no jump # 3)Can come from the building k+1, # one floor down, one jump added. # add points stored in building k # at the ith floor for all 3 cases dp[i][j][k] = max([dp[i - 1][j - 1][k - 1],dp[i - 1][j][k],dp[i - 1][j - 1][k + 1]])+ a[k][i - 1] # Return the maximum of points collected # over the top floor of all building after # engaging in permissible number of jumps ans = 0 for temp in range(buildings): ans = max(ans, dp[floors][jumps][temp]) return ans# Driver codeif __name__ == '__main__': # Number of floors # and number of jumps allowed. N = 5 M = 2 K = 3 # Number of points # at each floor of the buildings. a = [[4, 5, 1, 2, 10], [9, 7, 3, 20, 16], [6, 12, 13, 9, 8]] # Function call print(solve(a, N, M, K)) # This code is contributed by ipg2016107. |
C#
// C# implementation for the above approachusing System;class GFG{ static int solve(int[,] a, int floors, int jumps, int buildings) { /* dp(i, j, k) represents state of the maximum number of points that can be collected if the person is at ith floor having made at most j jumps and ended up at kth building. */ int [,,]dp = new int[floors + 1,jumps + 1,buildings + 1]; for (int i = 1; i <= floors; i++) { for (int j = 0; j <= jumps; j++) { for (int k = 0; k < buildings; k++) { // Base case: first floor if (i == 1) { // Cannot jump on ground floor // from any other building dp[i, j, k] = a[k, i - 1]; } // Base case: no jumps allowed else if (j == 0) { /* can choose one of the buildings and keep climbing up on the same building so can only take points from prev floor of same building and add current points */ dp[i, j, k] = dp[i - 1, j, k] + a[k, i - 1]; } // transition else { // first building if (k == 0) { /* 1)can come from building 1, one floor down, no jumps. 2)can come from building 2, one floor down, one jump added. add points stored in building 1 at the ith floor for both cases. */ dp[i, j, k] = Math.Max(dp[i - 1, j, k], dp[i - 1, j - 1, k + 1]) + a[k,i - 1]; } // Last Building else if (k == buildings - 1) { /* 1)Can come from building k-1 from one floor below, one jump added. 2)Can come from building k from one floor below, no jump added. add points stored in building k at the ith floor for both cases. */ dp[i, j, k] = Math.Max( dp[i - 1,j - 1,k - 1], dp[i - 1,j,k]) + a[k,i - 1]; } // intermediate buildings else { /* 1)Can come from the building k-1, one floor down, one jump added 2)Can come from the building k, one floor down, no jump 3)Can come from the building k+1, one floor down, one jump added. add points stored in building k at the ith floor for all 3 cases */ dp[i, j, k] = Math.Max( Math.Max( dp[i - 1, j - 1, k - 1], dp[i - 1, j, k]), dp[i - 1, j - 1, k + 1] ) + a[k, i - 1]; } } } } } // Return the maximum of points collected // over the top floor of all building after // engaging in permissible number of jumps int ans = 0; for (int building = 0; building < buildings; building++) ans = Math.Max(ans, dp[floors,jumps,building]); return ans; } // Driver code public static void Main(string[] args) { // Number of floors // and number of jumps allowed. int N = 5, M = 2, K = 3; // Number of points // at each floor of the buildings. int[,] a = { { 4, 5, 1, 2, 10 }, { 9, 7, 3, 20, 16 }, { 6, 12, 13, 9, 8 } }; // Function call Console.WriteLine(solve(a, N, M, K)); }}// This code is contributed by AnkThon |
Javascript
<script> // JavaScript Program to implement // the above approach function solve(a, floors, jumps, buildings) { /* dp(i, j, k) represents state of the maximum number of points that can be collected if the person is at ith floor having made at most j jumps and ended up at kth building. */ var dp = new Array(floors + 1); // create 2D for (let i = 0; i < dp.length; i++) { dp[i] = new Array(jumps + 1).fill(0); } // create 3D for (let i = 0; i < dp.length; i++) { for (let j = 0; j < dp[0].length; j++) { dp[i][j] = new Array(buildings + 1).fill(0); } } // Initializing dp with 0 for (let i = 1; i <= floors; i++) { for (let j = 0; j <= jumps; j++) { for (let k = 0; k < buildings; k++) { // Base case: first floor if (i == 1) { // Cannot jump on ground floor // from any other building dp[i][j][k] = a[k][i - 1]; } // Base case: no jumps allowed else if (j == 0) { /* can choose one of the buildings and keep climbing up on the same building so can only take points from prev floor of same building and add current points */ dp[i][j][k] = dp[i - 1][j][k] + a[k][i - 1]; } // transition else { // first building if (k == 0) { /* 1)can come from building 1, one floor down, no jumps. 2)can come from building 2, one floor down, one jump added. add points stored in building 1 at the ith floor for both cases. */ dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - 1][k + 1]) + a[k][i - 1]; } // Last Building else if (k == buildings - 1) { /* 1)Can come from building k-1 from one floor below, one jump added. 2)Can come from building k from one floor below, no jump added. add points stored in building k at the ith floor for both cases. */ dp[i][j][k] = Math.max( dp[i - 1][j - 1][k - 1], dp[i - 1][j][k]) + a[k][i - 1]; } // intermediate buildings else { /* 1)Can come from the building k-1, one floor down, one jump added 2)Can come from the building k, one floor down, no jump 3)Can come from the building k+1, one floor down, one jump added. add points stored in building k at the ith floor for all 3 cases */ dp[i][j][k] = Math.max( dp[i - 1][j - 1][k - 1], dp[i - 1][j][k], dp[i - 1][j - 1][k + 1]) + a[k][i - 1]; } } } } } // Return the maximum of points collected // over the top floor of all building after // engaging in permissible number of jumps let ans = 0; for (let building = 0; building < buildings; building++) ans = Math.max(ans, dp[floors][jumps][building]); return ans; } // Driver code // Number of floors // and number of jumps allowed. let N = 5, M = 2, K = 3; // Number of points // at each floor of the buildings. let a = [ [4, 5, 1, 2, 10], [9, 7, 3, 20, 16], [6, 12, 13, 9, 8] ]; // Function call document.write(solve(a, N, M, K));// This code is contributed by Potta Lokesh </script> |
Output:
70
Time Complexity: O(N*M*K) which means O(floors*jumps*buildings)
Auxiliary Space: O(N*M*K) which means O(floors*jumps*buildings)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
