Leetcode969: pancake sorting (medium, dynamic programming)

Catalog

1. Title Description

2. Problem solving analysis

3. Code implementation

---

1. Title Description

         See Leetcode969: Pancake sorting (medium, DFS).

        The first two solutions adopt the general algorithm framework , One is DFS, The other is BFS（Leetcode969: Pancake sorting (medium, BFS)）, It turned out to be embarrassing .DFS and BFS Of course, it is a heavy weapon with general combat power like a heavy tank , Based on these frameworks, many problems can be solved . But for a particular problem like this one , It feels like a golden marble hitting a bird , It takes a lot of ammunition, and the effect is not good . This is a small problem , After carefully analyzing the meaning of the question and get There is a very simple and clear solution to the key points , Although this solution is usually not universal . But after careful analysis, we can find that this problem is suitable to be solved by dynamic programming .

2. Problem solving analysis

         In fact, this problem can be regarded as an ascending sort problem by moving the position of elements , It's just a question ：

• The operation of moving position is limited , You can only reverse the problems of the previous elements
• To give a sequence of position adjustment operations

         First, consider moving the maximum value in the current sequence to the end of the list , This can be achieved in two steps ：

1. Rearrange the subsequence up to the maximum element upside down , Adjust the largest element to the front
2. Rearrange the whole sequence upside down , Adjust the largest element to the back

        Of course , If the largest element is already at the end , There is no need to adjust .

        When the maximum value is in place , Next, you only need to consider subsequences other than the maximum element .

        therefore , This problem can be regarded as a dynamic programming problem .

        Based on the above analysis , We can also know , It takes up to two steps to adjust the position of each element . Therefore, the upper limit of the total number of steps required is twice the length of the input sequence ！

3. Code implementation

from typing import List
from   collections import deque
import time

class Solution:    
    def pancakeSort(self, arr: List[int]) -> List[int]:
        def flip(k):
            for l in range(k//2):
                arr[l], arr[k-1-l] = arr[k-1-l], arr[l]

        kSeq = []
        def dp(n):
            # print('dp({0}), {1}'.format(n,arr[:n]))
            if n == 1: # baseline case
                return
            for k in range(n):
                if arr[k] == n:
                    if k == n-1: # The maximum number is already in its proper position
                        break
                    else:     
                        if k > 0:
                            flip(k+1)
                            kSeq.append(k+1)
                        flip(n)                        
                        kSeq.append(n)                                       
                    break
            dp(n-1)        
            
        dp(len(arr))
        return kSeq

Back to the general catalogue of this note series ： Slow ploughing by stupid cattle Leetcode Problem solving notes ( Dynamic update ...)https://chenxiaoyuan.blog.csdn.net/article/details/123040889