This study investigates the minimum maximal deviation of a mathematical problem known as the Fibonacci Walk, proposed by Instructor Sen-Peng and published in Science Monthly. The problem is described as follows: Fibonacci starts from the origin and walks along a number line for five steps. The step lengths are 1, 1, 2, 3, and 5, corresponding to the first five terms of the Fibonacci sequence, and at each step he may choose either the positive or negative direction. His goal is to ensure that, throughout the entire walk, the farthest position reached is as close to the origin as possible. In addition to analyzing the original Fibonacci sequence, this study further generalizes the problem to Fibonacci-type sequences that share the same recurrence relation but have different initial conditions.The main results are as follows: 1.Analyzing the minimum maximal deviation of increasing positive integer sequences and deriving the corresponding formula for generalized Fibonacci-type sequences. 2.Investigating the distribution of the minimum maximal deviation within the optimal walk and directional selection properties of the last six steps. 3.Providing two methods for counting the number of corresponding optimal paths.