Минимальные этапы

Ответ 1

Одна идея состоит в том, что на любой итерации вам нужны значения только для r/3 - r. Поэтому вы можете отказаться от 1/3rd массива.

Я не знаком с Java, но с C++ вы можете использовать double ended queue (deque):

Вы продолжаете добавлять в deque со спины.
Если i = 6, вам не нужны bu[0] и bu[1]. Таким образом, вы выталкиваете два элемента из передней части очереди.

Случайный доступ [ ] поддерживается контейнером deque.

РЕДАКТИРОВАТЬ: Также, как указано в комментариях, вы должны изменить свой тип данных на меньший размер, поскольку максимальное количество шагов должно быть порядка ( (log N) to base 2)

EDIT2: Как отметил Дюкелинг, похоже, что в Java нет готовой хорошо подходящей реализации для deque, которая не будет компрометировать по сложности времени. Вы можете подумать о том, чтобы реализовать его по-своему, как это делает С++ (я слышал, что он реализован как вектор векторов с малым размером внутренних векторов по сравнению с общим количеством элементов).

Ответ 2

UPDATE: здесь обновлен код, который я фактически протестировал несколько, и я верю, что приходит к тем же ответам для n от 1 до 100000. Я оставляю исходный ответ ниже для справки. Недостатком было "умное" использование MAX_INT. Я забыл, что будут случаи, когда я пропустил возможность -1, но число также не будет делиться на 2 или 3. Это решает, возвращая значение null, чтобы означать, что "этот путь бессмыслен для дальнейшего изучения".

public static int steps(int n) {
    return steps(n, 0);
}
private static Integer steps(int n, int consecutiveMinusOnes) {
    if (n <= 1) {
        return 0;
    }
    Integer minSteps = null;
    if (consecutiveMinusOnes < 2) {
        Integer subOne = steps(n - 1, consecutiveMinusOnes + 1);
        if (subOne != null) {
            minSteps = 1 + subOne;
        }
    }
    if (n % 2 == 0) {
        Integer div2 = steps(n / 2, 0);
        if (div2 != null) {
            if (minSteps == null) {
                minSteps = div2 + 1;
            } else {
                minSteps = Math.min(minSteps, 1 + div2);
            }
        }
    }
    if (n % 3 == 0) {
        Integer div3 = steps(n / 3, 0);
        if (div3 != null) {
            if (minSteps == null) {
                minSteps = div3 + 1;
            } else {
                minSteps = Math.min(minSteps, 1 + div3);
            }
        }
    }
    return minSteps;
}

Я считаю, что это может сработать, но я этого не доказал. Этот алгоритм основан на идее, что единственная причина для вычитания одной из них заключается в том, чтобы приблизить вас к числу, делящемуся на 2 или 3. По этой причине вам действительно не нужно применять шаг вычитания на один более двух раз последовательно, потому что если k% 3 == 2, то k - 2% 3 == 0, и вы можете разделить на три. Вычитание еще раз потребует усилий (вы также пройдете хотя бы на один четный номер, так что лучшая разница с двухступенчатой ​​возможностью появится). Это означает "сверху вниз", "рекурсивный" подход, и вы можете смешать в некоторой мемонизе, если хотите:

public static int steps(n) {
    return steps(n, 0);
}
private static int steps(int n, int consecutiveMinusOnes) {
    if (n <= 1) {
        return 0;
    }
    int minSteps = Integer.MAX_VALUE;
    if (consecutiveMinusOnes < 2) {
        minSteps = 1 + steps(n - 1, consecutiveMinusOnes + 1);
    }
    if (n % 2 == 0) {
        minSteps = Math.min(minSteps, 1 + steps(n / 2, 0));
    }
    if (n % 3 == 0) {
        minSteps = Math.min(minSteps, 1 + steps(n / 3, 0));
    }
    return minSteps;
}

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Как я сказал выше, я не доказал, что этот метод работает. Я также не тестировал эту конкретную реализацию. Я тоже не делал воспоминаний, потому что я ленив. Во всяком случае, я надеюсь, что даже если это не совсем сработает, вы получите некоторые идеи о том, как изменить свой подход.

Ответ 3

Это работает:)

import java.util.Scanner;
public class MinimumStepToOne {

 public static void main(String[] args){
    Scanner sscan = new Scanner(System.in);
    System.out.print("Give a no:" + " ");

    int n = sscan.nextInt();
    int count = 0;
    for(int i = 0; n > 1; i++){

        if(n%2 == 0){n /= 2; count++;}
        else if(n%3 == 0){ n /= 3; count++;}
        else { n -= 1; count++;}

    }
    System.out.println("your no is minimized to: " + n);
    System.out.println("The min no of steps: " + count);    
 }
}