【华为OD题库-047】求最小步数-java

本文介绍: 求从坐标零点到坐标点n的最小步数，一次只能沿横坐标轴向左或向右移动2或3.注意:途径的坐标点可以为负数坐标点n 输出从坐标零点移动到坐标点n的最小步数42从坐标零点移动到4，最小需要两步，即右移2，再右移2。

两种方案：

package hwod;

import java.util.LinkedList;
import java.util.Scanner;

public class TheMinStep {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(minStep(n));

    }
//动态规划
    private static int minStep(int n) {
        if (n == 1) return 2;
        LinkedList<Integer&gt; queue = new LinkedList<&gt;();
        queue.addLast(2);
        queue.addLast(1);
        queue.addLast(1);
        for (int i = 4; i <= n; i++) {
            int first = queue.pollFirst();
            int second = queue.peekFirst();
            queue.addLast(Math.min(first, second) + 1);
        }
        return queue.peekLast();
    }
// 数学解法
    private static int minStep2(int n) {
        if (n == 1) return 2;
        int a = n / 3, b = n % 3;
        if (b == 0) return a;
        return a + 1;
    }
}