Найти все пути вниз по лестнице? - PullRequest
15 голосов
/ 24 февраля 2011

Мне дали следующую проблему в интервью:

Учитывая лестницу с N ступенями, вы можете подняться на 1 или 2 ступени каждый раз.Выведите все возможные пути, идущие снизу вверх.

Например:

N = 3

Output :
1 1 1
1 2
2 1

При опросе я только что сказал использовать динамическое программирование.

S (n) = S (n-1) +1 или S (n) = S (n-1) + 2

Однако во время интервью я не очень хорошо писалхороший код для этого.Как бы вы описали решение этой проблемы?

Спасибо, действительно!

Ответы [ 13 ]

0 голосов
/ 18 декабря 2012

может быть, я ошибаюсь .. но это должно быть:

S(1) =0
S(2) =1

Здесь мы рассматриваем перестановки таким образом

S(3) =3
S(4) =7
0 голосов
/ 28 июня 2011

Полный код C-Sharp для этого

 void PrintAllWays(int n, string str) 
    {
        string str1 = str;
        StringBuilder sb = new StringBuilder(str1);
        if (n == 0) 
        {
            Console.WriteLine(str1);
            return;
        }
        if (n >= 1) 
        {
            sb = new StringBuilder(str1);
            PrintAllWays(n - 1, sb.Append("1").ToString());
        }
        if (n >= 2) 
        {
            sb = new StringBuilder(str1);
            PrintAllWays(n - 2, sb.Append("2").ToString());
        }
    }
0 голосов
/ 24 февраля 2011

Это проблема взвешенного графика.

  • От 0 вы можете добраться до 1 только одним способом (0-1).
  • Вы можете добраться до 2 двумя способами, от 0и от 1 (0-2, 1-1).
  • Вы можете добраться до 3 тремя способами, от 1 до 2 (у 2 есть два пути).
  • Вы можете получить до 4пять способов, из 2 и из 3 (2 имеет два пути, а 3 имеет три пути).
  • Вы можете получить до пяти восьми способов, ...

Рекурсивная функция должнабыть в состоянии справиться с этим, работая в обратном направлении от N.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...