Here is the problem statement .
We will solve this problem with dynamic approach mening that we will get the solution for current cell (X,Y) with the help of (X-1,Y) (X-1,Y-1),(X-1,Y+1). We will call teh given array A. We will also keep another array B where B[i][j] will show that maximum number of stones we can collect . INitially every element of the first row of the array B equals to every element of the first row of array A, the others have a value of 0. Now we need to loop over array B and for every coordinate (X,Y) we need to see if we can update B[X+1][Y] , B[X+1][Y-1] or B[X+1][Y+1]. Then we need to find the maximum of the last row of the array B and print it out.
We will solve this problem with dynamic approach mening that we will get the solution for current cell (X,Y) with the help of (X-1,Y) (X-1,Y-1),(X-1,Y+1). We will call teh given array A. We will also keep another array B where B[i][j] will show that maximum number of stones we can collect . INitially every element of the first row of the array B equals to every element of the first row of array A, the others have a value of 0. Now we need to loop over array B and for every coordinate (X,Y) we need to see if we can update B[X+1][Y] , B[X+1][Y-1] or B[X+1][Y+1]. Then we need to find the maximum of the last row of the array B and print it out.
No comments:
Post a Comment