Подсчитайте пути до n-й ступеньки (порядок не имеет значения) - PullRequest
Новая
       83

Подсчитайте пути до n-й ступеньки (порядок не имеет значения)

1 голос
/ 13 июля 2020

Есть N лестниц, и человек, стоящий внизу, хочет добраться до вершины. Человек может подниматься по 1 или 2 ступенькам за раз. Подсчитайте количество способов, которыми человек может добраться до вершины (порядок не имеет значения). Примечание. Порядок не имеет значения, средства для n = 4 {1 2 1}, {2 1 1}, {1 1 2} считаются одинаковыми.

https://practice.geeksforgeeks.org/problems/count-ways-to-nth-stairorder-does-not-matter/0

Итак, я пытался решить этот вопрос, и проблема, с которой я столкнулся, заключается в том, что я не понимаю, как мы решаем подобные вопросы, когда порядок не имеет значения? Мне удалось решить вопрос, когда порядок имел значение, но я не могу разработать лог c, чтобы решить эту проблему.

Это код, который я написал, когда порядок имел значение 

long int countWaysToStair(long int N)
{
    if(N == 1 || N == 2)
    return N;

    long int dp[N+1];

    dp[0] = 1;
    dp[1] = 1;

    dp[2] = 2;

    for(int i=3;i<=N;i++)
    {
      dp[i] = dp[i-1] + dp[i-2];
    } 
    return dp[N];
}

Ввод: 4 Ожидаемый результат: 3 Мой вывод: 5

1 Ответ

9 голосов
/ 13 июля 2020

Считайте, что у вас N лестниц. Прежде всего, вы должны понять, является ли N нечетным или четным.

Если четное, то оно будет кратным 2: N = 2 * S, где S - количество пар лестниц.

Предположим, N = 6 и S = ​​3. Ваше первое решение - {2,2,2}. чем вы можете заменить первые 2 лестницы на 1 + 1 ступеньки, и у вас есть второе решение {1, 1, 2, 2}. Поскольку порядок не имеет значения, перейдем к следующей паре, и у нас будет третье решение {1, 1, 1, 1, 2}, а затем четвертое {1, 1, 1, 1, 1, 1}

Для N = 2 * S количество возможных решений равно S + 1.

Теперь предположим, что N нечетно и N = 2S + 1. Пусть N = 7 и S = ​​3. Наши решения: {2 , 2,2,1}, {1,1,2,2,1}, {1,1,1,1,2,1} и {1,1,1,1,1,1,1}. Опять же, количество решений равно S + 1

Теперь ваш алгоритм довольно прост: 

return N/2 + 1
...