способы достижения n-й ступени, но с заданным условием

Question

Есть n лестница, человек, стоящий внизу, хочет достичь вершины. Человек может подниматься либо на 1 ступень, либо на 2 ступеньки одновременно.

Теперь я хочу найти минимальное количество необходимых шагов, которые делятся на данное число m .

Вот программа java, которую я создал, используя в качестве ссылки , которая используется для печати возможных шагов:

public static void main(String args[]) {
        int n = 10, m = 2;
        List<Integer> vals = new ArrayList<>();
        Set<String> set = new TreeSet<>(Comparator.reverseOrder());
        ClimbWays(n, 0, new int[n], vals, set);

        set.forEach(a -> {
            System.out.println(a + " : " + a.length());
        });
    }

    public static void ClimbWays(int n, int currentIndex, int[] currectClimb, List<Integer> vals, Set<String> set) {
        if (n < 0)
            return;

        if (n == 0) {
            vals.add(currentIndex);
            int last = 0;
            StringBuilder sb = new StringBuilder();
            for (int i = currentIndex - 1; i >= 0; i--) {
                int current = currectClimb[i];
                int res = current - last;
                last = current;
                sb.append(res);
            }
            String s = sb.toString();
            char[] c = s.toCharArray();
            Arrays.sort(c);
            s = new String(c);
            set.add(s);
            return;
        }

        currectClimb[currentIndex] = n;
        ClimbWays(n - 1, currentIndex + 1, currectClimb, vals, set);
        ClimbWays(n - 2, currentIndex + 1, currectClimb, vals, set);
    }

Вывод программы:

22222 : 5
112222 : 6
1111222 : 7
11111122 : 8
111111112 : 9
1111111111 : 10

Теперь для шагов 10, если я хочу получить минимальные шаги, кратные m = 2, то решение будет 112222, в котором количество необходимых шагов равно 6.

Эта программа в основном находит все возможные пары затем добавить их в набор деревьев. Затем я могу l oop через этот набор и получить минимальный элемент, делимый на заданный вход m.

Есть ли лучший подход для этого?

Answer 1

Поскольку человек может подниматься не более 2 шагов одновременно, минимальное количество шагов для подъема по лестнице составляет

x = n/2 if n is even
x = n/2 + 1 if n is odd

Теперь вам нужно найти минимальное количество шагов, чтобы подняться по лестнице который делится на м. Это означает, что вам нужно найти число рядом с x, которое делится на m.

if x%m == 0 then x is your answer
if x%m != 0 then ((x/m) + 1) * m is your answer.

Теперь поговорим о вашем примере

For n = 10, 
x = n/2 = 5,
x%m = 5 % 2 = 1 != 0
Thus ans = ((5/2) + 1) * 2 = 6