How to solve DP: part 3

1269. Number of Ways to Stay in the Same Place After Some Steps

I’d like to illustrate the DP problem-solving process by one example from leetcode.

It is 1269. Number of Ways to Stay in the Same Place After Some Steps.

Link to this problem is here:

Account Login - LeetCode

Please read the problem description from leetcode. In order to solve the problem, let’s build the solution from some baby examples. For the solution:S means to stay, L means moving to the left and R means moving to the right.

Firstly do not consider the moving is bounded by the arrLen case.

Example 1 : Steps = 1, arrLen=2:

S.

Example 2 :Steps = 2, arrLen=2:

S, S; R, L

Example 3:Steps = 3, arrLen=3:

SSS, SRL, RSL, RLS

Example 4:Steps = 4, arrLen=4:

case 1: 4 Ss

SSSS

case 2: 2 Ss

_R_L_(3 choose 2 to put S), _R_L_ (3 choose 1 to put SS)

case 3: 0 Ss

R_R_(2 choose 2 to put L), R_R_(2 choose 2 to put LL)

Example 5:Steps = 5, arrLen=5:

case 1: 5Ss

SSSSS

case 2:4Ss

no solution in this case. SSSS the rest location is an odd number, it is impossible as we need pairs of RL to move back to zero.

case 2: 3Ss

_S_S_S_ (4 choose 2 to put R and L separately)

_S_S_S_(4 choose 1 to put RL)

case 3: 2Ss (odd remaining positions, no solution in this case)

case 4: 1S

4a) put RRLL

R_R_(2 choose 2 to put L), R_R_(2 choose 2 to put LL)

4b) put S into each result of 4a)

_R_R_L_L_ (5 choose 1 to put S)

From those examples, can we build a recursion approach without considering about bounding by the arrLen case?

We can have a simple recursion method by sum up all the cases from 0 S to steps Ss. Where S means the number of Ss and RL means the number of R and L.

S+RL = steps

res = sum(dp(S, RL) for S in range(steps+1))

Based on this, rewrite the solutions for the previous examples.

Example 1 : Steps = 1, arrLen=2:

sum(dp(0, 1), dp(1, 0))

Example 2 :Steps = 2, arrLen=2:

sum(dp(0,2), dp(1,1), dp(2,0))

Example 3:Steps = 3, arrLen=3:

sum(dp(0,3), dp(1,2), dp(2,1),dp(3,0))

Example 4:Steps = 4, arrLen=4:

sum(dp(0,4), dp(1,3), dp(2,2),dp(3,1),dp(4,0))

Example 5:Steps = 5, arrLen=5:

sum(dp(0,5), dp(1,4), dp(2,3),dp(3,2),dp(4,1),dp(5,0))

The problem is well organized, however, what is the solution? And what is the time complexity of this solution?

Firstly: when RL is an odd number, the result is 0, as we need paris of RL to move back to ZERO.

Secondly, dp(n, m) = …

It is really hard to find transitions to reduce the problem into smaller subproblems.

Now let’s think about the problem in another way: how can we reach a specified position say position n in an array, or in a one-dimensional line?

We can move:

1. from position n to position n by the action stay

2. from position n-1 to position n by the action of moving to the right

3. from position n+1 to position n by the action of moving to the left.

These 3 choices are shown in Figure 1.

Figure 1: three ways to move to position n.

From Figure 1, we can find the state transitions as:

dp(n, step+1) = dp(n-1, step)+dp(n, step) + dp(n+1, step)

Then we can find the solution of the problem. We can solve the problem either by bottom-up or top-down.

Before providing the solution, let’s go back to our baby examples to build the transitions by using this approach.

Example 1 : Steps = 1, arrLen=2:

sum(dp(-1, 0),dp(0,0),dp(1,0))

Example 2 :Steps = 2, arrLen=2:

sum(dp(-1, 1),dp(0,1),dp(1,1))

Example 3:Steps = 3, arrLen=3:

sum(dp(-1, 2),dp(0,2),dp(1,2))

Example 4:Steps = 4, arrLen=4:

sum(dp(-1, 3),dp(0,3),dp(1,3))

Example 5:Steps = 5, arrLen=5:

sum(dp(-1, 4),dp(0,4),dp(1,4))

Here comes the solutions.

Top-down approach (284 ms)

https://github.com/liketheflower/leet_code_jimmy/blob/master/dp/1269/solution2.py

Bottom-Up approach (290 ms)

https://github.com/liketheflower/leet_code_jimmy/blob/master/dp/1269/solution1.py

Time complexity analysis:

a) Naive approach and complexity.

In order to have a better understanding of the problem, it will be nice to have an analysis of the naive approach. Naively, we can move forward by using a BFS approach until reach the number of steps. For each state, we can generate a new state by stay, left and right. The state can be represented as (position, step).

The naive approach is illustrated in Figure 2.

Figure 2: a naive way to consider all the possibilities.

Naively, we will have a geometric sequence of computation(3, 9, 27, …) and number of nodes is 3*(1–3^n)/(1–3) = 3*(3^n-1)/2=1.5*3^n-1.5. Hence the time complexity is O(3^n).

We can prune the negative positions and combine nodes with the same states as shown in Figure 3.

Figure 3: prune and combine

After pruning and combining, we can have the updated Figure 4.

Figure 4: after pruning and combing.

From figure 4, we can have a better understanding of the DP solution, also we can easily figure the time complexity of DP is reduced to O(n²) where n is the number of steps. The reason that it is O(n²) is 1+2+3+4…+n = n(n+1)/2.

If you are reading here, it will be very natural to have a BFS solution.

BFS solution (1000 ms. When changing the dp from dict to list, the run time is reduced to 752 ms)

https://github.com/liketheflower/leet_code_jimmy/blob/master/dp/1269/bfs.py

BFS solution by using list (752 ms)

BFS solution by pruning too far away to go back to original position branches (pos+action<=steps-step-1)to further reduce the time to 584 ms.

BFS solution by using deque, can speed up a little bit.

Reference

Account Login - LeetCode

https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/discuss/436201/Python-Cache-DP