LeetCode 931. Minimum Falling Path Sum

Link:- https://leetcode.com/problems/minimum-falling-path-sum/

Summary:

Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row and chooses one element from each row.  The next row's choice must be in a column that is different from the previous row's column by at most one.

For Example:
Input:

[[1,2,3],[4,5,6],[7,8,9]]

Output:
12

Logic:

Given array A with row ->n and column ->n

now create matrix say ans[n][m]

copy first row of A into ans

i.e ans[0] = A[0]

Why?

since we can start from any column in first row

now for rest of the row and column say i and j (1<=i<n, 0<=j<m)

ans[i][j] = A[i][j] + min(ans[i][j-1], ans[i-1][j-1], ans[i-1][j+1]

return min(ans[n-1])

i.e minimum of all values in last row

Why?

because we can end at any column of last row.

To View My Solution:

https://github.com/shivam04/codes/blob/master/leetcode/minimum-falling-path-sum.cpp

LeetCode 1140. Stone Game II

Link:- https://leetcode.com/problems/stone-game-ii/

Summary:

Alex and Lee continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].  The objective of the game is to end with the most stones. 

Alex and Lee take turns, with Alex starting first.  Initially, M = 1.

On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

For Example:
Input:

[2,7,9,4,4]

Output:
10

Logic:

You can easily solve this question recursion.

So Alex will try to get the maximum point as he is playing optimally

if player == 1 (or Alex)

 alexPoint = max(alexPoint, sum[s to s+x-1]  stoneGameIIUtil(piles, s+x, max(x,m), n ,1-p));

also, Lee is playing optimally and try to reduce Alex points

if player == 0 (or Lee)

 alexPoint = min(alexPoint, stoneGameIIUtil(piles, s+x, max(x,m), n ,1-p));

1<=x<2*M

Will this solution gives TLE?

Yes

as 1<=N<=100 (total number of piles)

We can't use recursion here.

How can we optimize it?

One solution that I think of is using memorization. We can create a matrix say dp

and store current state dp[s][m][p]

s -> starting index

m -> for picking stones from piles i.e (1<=x<=2*m)

p -> 0/1 (Lee/Alex)

Now if we reach this state again we don't need to compute again and return dp[s][m][p]

(Yahi battein to bad me yaad  ayengi 😛)

Can we further optimize it?

Yes.

For calulationg sum[s to s+x-1]

we can use prefixSum array 

so sum[s to s+x-1] will be prefixSum[s+x-1] - prefixSum[s-1]

To View My Solution:

https://github.com/shivam04/codes/blob/master/leetcode/stone-game-ii.cpp