[C ++ & rust] leetcode no.1269 брой планове

题目

Има масив с дължина Arrlen и започва с указател при индекс 0.

Във всяка стъпка можете да преместите показалеца наляво или надясно или да спрете на място (показателят не може да бъде преместен в диапазона на масива).

Давам ви две цели числа стъпки и arrlen, моля, изчислете и върнете: След като СТЪПКИ току-що се изпълни, показалецът все още сочи към броя на схемите при индекс 0.

Тъй като отговорът може да е голям, моля, върнете резултатите от програмата номер 10 ^ 9 + 7.

Пример 1

Въведете: стъпки = 3, arrlen = 2

Резултат: 4

Обяснение: След стъпка 3 има общо 4 различни начина за спиране на индекси.

Надясно, наляво, не мърдайте

Не се движете, надясно, наляво

Надясно, не мърдай, наляво

Не мърдайте, не мърдайте, не мърдайте

Пример 2:

Въведете: стъпки = 2, arrlen = 4

Резултат: 2

Обяснение: След 2 стъпки има два различни начина за спиране на индекси.

Надясно, наляво

Не мърдайте, не мърдайте

Пример 3:

Въведете: стъпки = 4, arrlen = 2

Резултат: 8

подкана:

1 <= стъпки <= 500

1 <= arrLen<= 10^6

Източник: Линк към Leetcode: https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps авторските права принадлежат на цялата мрежа. Ако бизнес препечатка, моля, свържете се с официалното разрешение, моля, посочете източника на нетърговска препечатка.

思路分析

Тази тема всъщност изисква малко способност за наблюдение, първо виждаме две отношения между Arr и Steps. Всъщност Пример 2 и Пример 3 показват това. За пример 2, 4 дължини на ArR не са непременно. Тъй като общо две стъпки, нагоре вляво е една стъпка, невъзможно е да се отиде до решетката отзад и ние приемаме, че има неограничена дължина на Arr и STEP, равна на 5 условия, може да се види, че нагоре to Arr [1] Местоположението, тъй като веднъж отиде до Arr [2], няма да се върне (било е три стъпки надясно и също се нуждае от три стъпки, но само 5 стъпки). Вижте правилата

steps2345最大回头的位置1(0->1->0)12(0->1->2->1->0)2最大位置对应的arr_len2233

Следователно, ние обобщаваме заключение, че когато Arr е по-голямо от (STEP ", има излишно място, можете да използвате (STEP, 2 + 1), за да замените излишъка Arr, за да постигнете целта за намаляване на изчислението.

Този въпрос трябва да се използва, защото много фактори, като този въпрос е въпрос за симулация, той ни насочва да симулираме, но трябва да изтече време, можете да използвате DFS, ще изтече време за изчакване, това ще ни насочи да мислим към DP, и това Има също така много критична подкана, която трябва да получим само броя на сценариите, не е нужно да получаваме нищо. Това също е точка, която питащият обмисля, тоест аз ви насочвам да мислите така, но това е просто начин на мислене, не ви позволява да го направите в тази идея. Това също е предложена Желязна лига на DP. Когато се появи темата, броят на „отговорите“, „номерът на пътя“, „Номерът на решението“, което показва, че темата не е всяка конкретна схема, а броят на схемите. В този случай 99% от случая се извършва с помощта на DP. Количеството DP рекурсивно обикновено е свързано с отговора на отговора и дори може директно да извлече самия отговор. Това que

действието е да стартирате отговор директно. С оглед на броя на сценариите за изчисляване, ние задаваме DP масив, Arr [i] представлява броя на решенията на Arr [i], така че да можем да прочетем Arr [0] директно след доставката, можете да получите отговора . Рекурсивното също е много лесно за мислене, защото когато STEP променя всяка промяна, се приема, че човек може да посочи I броя указатели, следващата стъпка може да сочи към i-1 или i или i + 1 (без да се взема предвид границата условие), тогава имаме броя на сценариите и ще трябва да добавим предишния ARR [i], така че да можете да симулирате стъпка по стъпка.

След това можем да видим кода директно.

C++代码

Const int mod = 1e9 + 7;

Решение за клас {

ОБЩЕСТВЕНО:

INT Numways (int Stes, int Arr_len) {

INT n = min (Arr_len, стъпки / 2 + 1);

Вектор Arr (n, 0);

Arr [0] = 1;

за (int i = 0; i < стъпки; ++i) {

Вектор Arr_TMP (n, 0);

за (int i = 0; i < n && arr[i] > 0; ++i) {

за (int j = max(0, i - 1); j <= min(n - 1, i + 1); ++j) {

Arr_TMP [J] + = Arr [i];

Arr_TMP [J]% = MOD;

}

}

Arr = Преместване (arr_tmp);

}

Връщане на Arr [0];

}

};

Rust代码

Impl solution {

pub fn num_ways(стъпки: i32, arr_len: i32) -> i32 {

Нека n = arr_len.min (Стъпки + 2) / 2) като размер;

Нека Mut Arr = VEC! [0; Н];

Arr [0] = 1;

For i Iin 0..sts {

Нека MUT ARR_TMP = VEC! [0; Н];

За i в 0..n {

ако arr[i] > 0 {

За J в (1.max (i) - 1) .. = (((N-1) .min (i + 1)) {

Arr_TMP [J] + = Arr [i];

Arr_tmp [j]% = (1E9 AS i32 + 7);

}

} else {

Прекъсване;

}

}

Arr = arr_tmp;

}

Пристигане [0]

}

}

Трябва да е тук! Не! Днес също има специална програма по въпроса, все още имам нова идея!

Онлайн коленичил като математически трол, доказах, че времевата сложност може да достигне O (стъпки), но не е възможно да поискате формулата за спазване на стъпки = 10, arr_len = 10

[0, 1, 1, 0, 0, 0, 0, 0]

[0, 2, 2, 1, 0, 0, 0, 0]

[0, 4, 5, 3, 1, 0, 0, 0]

[0, 9, 12, 9, 4, 1, 0, 0]

[0, 21, 30, 25, 14, 5, 1, 0]

[0, 51, 76, 69, 44, 20, 6, 0]

[0, 127, 196, 189, 133, 70, 26, 0]

[0, 323, 512, 518, 392, 229, 96, 0]

[0, 835, 1353, 1422, 1139, 717, 325, 0]

[0, 2188, 3610, 3914, 3278, 2181, 1042, 0]

Окончателният отговор е 2188, но всъщност не е нужно да мислим, че могат да се наблюдават толкова много линии.

(Спазвайте коефициента, няколко реда, започващи от горната таблица)

2188

= 1 * 835 + 1 * 1353

= 2 * 323 + 2 * 512 + 1 * 518

= ...

= 21 ** 2 + 30 ** 2 + 25 ** 2 + 14 ** 2 + 5 ** 2 + 1 ** 2

Следователно трябва само да изчислите тази линия, да попитате квадрата и можете да получите отговора. (Ако Steps е странно, може да се наложи да преброите два реда, но все още o (стъпки)) и аз се позовавам на Yang Hui Triangle Solution Https://leetcode-cn.com/problems/pascals-triangle-ii/solution/yang -hui -san-jiao-ii-by-leetcode-solutio-shuk / е алгоритъмът на N (N) за намиране на N-тия ред, така че мисля, че това също е решено, надявам се математическият трол да ми помогне да изчисля!