Leetcode skimming -- guess the size of numbers II 375 medium

Guess the size of the numbers II Ideas and source code
     Guess the size of the numbers II The title of is shown in the figure below , This problem belongs to mathematics and dynamic programming , It mainly investigates the use of dynamic programming methods and the understanding of mathematical ideas of the topic . The title of this article, the author thought 2 Methods , They are memory search method and dynamic programming method , The memory search method uses Java Compiling , The dynamic programming method uses Python Compiling , Of course, this may not be the optimal solution , I also hope you guys can give a faster algorithm .

     I think this problem can be solved by using the idea of memory search method , Initialize the parameters first , Then define a circular recursive function , The logic implemented inside the function is as follows ： Pass in the lower and upper limit parameters , Judge whether the lower limit parameter is greater than or equal to the upper limit parameter , If so, go straight back 0 And end , Judge whether the corresponding array value of the current position is not 0, If yes, the current result of the array will be returned directly . Start traversing the loop , Find the maximum value of nearby elements , Then compare the historical value with the maximum value of nearby elements , Save the smaller value , Until the loop traversal ends and the historical minimum value is saved to the current element value . Recursively search with this logic until the end and finally return the result . Then according to this idea, our Java The code is as follows ：

# Fire breathing dragon and water arrow turtle 
class Solution {
    static int N = 210;
    static int[][] arr = new int[N][N];
    public int getMoneyAmount(int n) {
        return searchDFS(1, n);
    }
    int searchDFS(int a, int b) {
        if (a >= b){
            return 0;
        }
        if(arr[a][b] != 0){
            return arr[a][b];
        }
        int res = 0x3f3f3f3f;
        for (int jr = a; jr <= b; jr++) {
            int ind = Math.max(searchDFS(a,jr-1), searchDFS(jr+1,b))+jr;
            res = Math.min(res,ind);
        }
        arr[a][b] = res;
        return res;
    }
}

     obviously , Our memory based search method works well , Dynamic programming can also be used to solve . First initialize a dynamic programming array and assign values , Then start traversal , Each value of dynamic programming is equal to the sum of the subscript and the value on the left , Then inside the area , Compare and assign values according to the rules of the transfer equation of the dynamic programming of the problem , Until the loop ends and returns the final result . So according to this idea, we can solve , Here is Python Code ：

# Fire breathing dragon and water arrow turtle 
class Solution:
    def getMoneyAmount(self, n: int) -> int:
        dpArr = [[0] * (n + 1) for _ in range(n + 1)]
        for ir in range(n - 1, 0, -1):
            for jr in range(ir + 1, n + 1):
                dpArr[ir][jr] = jr + dpArr[ir][jr - 1]
                for kr in range (ir, jr):
                    dpArr[ir][jr] = min(dpArr[ir][jr], kr + max(dpArr[ir][kr-1],dpArr[kr+1][jr]))
        return dpArr[1][n]

     As a result Java The efficiency of version memory search method is good , and Python The speed of the version of dynamic programming method is relatively general , But there should be more ways to further speed up , I hope friends can give me more advice , Thank you very much .