[C ++ & rust] leetcode č.1269 počet plánů

题目

Existuje pole délky Arrlen a začíná ukazatelem na indexu 0.

V každém kroku můžete posunout ukazatel doleva nebo doprava nebo se zastavit na místě (ukazatel nelze přesunout do rozsahu pole).

Dejte vám dva celočíselné kroky a arrlen, vypočítejte a vraťte se: Po provedení KROKŮ bude ukazatel stále ukazovat na počet schémat na indexu 0.

Vzhledem k tomu, že odpověď může být velká, vraťte prosím výsledky programu číslo 10 ^ 9 + 7.

Příklad 1

Zadejte: kroky = 3, arrlen = 2

Výstup: 4

Vysvětlení: Po kroku 3 existují celkem 4 různé způsoby, jak zastavit indexy.

Doprava, doleva, nepohybujte se

Nepohybujte se doprava ani doleva

Doprava, nehýbejte se, doleva

Nehýbejte se, nehýbejte se, nehýbejte se

Příklad 2:

Zadejte: kroky = 2, arrlen = 4

Výstup: 2

Vysvětlení: Po 2 krocích existují dva různé způsoby, jak zastavit indexy.

Doprava, doleva

Nehýbej se, nehýbej se

Příklad 3:

Zadejte: kroky = 4, arrlen = 2

Výstup: 8

výzva:

1 <= kroků <= 500

1 <= arrLen<= 10^6

Zdroj: Odkaz na Leetcode: https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps autorská práva patří síti all . Pokud se jedná o obchodní dotisk, kontaktujte prosím oficiální autorizaci, uveďte zdroj nekomerčního dotisku.

思路分析

Toto téma ve skutečnosti vyžaduje trochu pozorovací schopnosti, nejprve vidíme dva vztahy mezi Arrem a Stepsem. Příklad 2 a příklad 3 to ve skutečnosti ukazují. V příkladu 2 nebyly nutně 4 délky ArR. Protože celkem dva kroky, nahoře vlevo je jeden krok, není možné přejít k mříži za sebou a předpokládáme, že existuje neomezená délka Arr a STEP rovna 5 podmínkám, je vidět, že nahoru to Arr [1] Místo, protože jakmile šel do Arr [2], už se nevrátí (byly to tři kroky doprava a také to potřebuje tři kroky, ale jen 5 kroků). Podívejte se na pravidla

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

Proto shrneme závěr, že když je Arr větší než (STEP ", je tam nadměrné místo, můžete použít (STEP, 2 + 1) k nahrazení přebytečného Arr, abyste dosáhli účelu snížení výpočtu).

Tato otázka by se měla použít, protože mnoho faktorů, například tato otázka je otázkou simulace, nás vede k simulaci, ale musí vypršet časový limit, můžete použít DFS, bude to časový limit, to nás povede k zamyšlení do DP, a to Existuje také velmi kritický bod výzvy, který potřebujeme pouze k získání počtu scénářů, nepotřebujeme získat nic. To je také bod, který tazatel zvažuje, to znamená, že vás navádím, abyste si to mysleli, ale je to jen způsob myšlení, který vám to v této myšlence nedovolí. Toto je také navrhovaná Železná liga DP. Když se téma objeví, počet „odpovědí“, „číslo cesty“, „číslo řešení“, což znamená, že tématem není každé konkrétní schéma, ale počet schémat. V tomto případě je 99 % případů provedeno pomocí DP. Množství rekurzivního DP obecně souvisí s odpovědí na odpověď a může dokonce přímo odvodit samotnou odpověď. Tato que

je přímo spustit odpověď. S ohledem na počet scénářů k výpočtu jsme nastavili pole DP, Arr [i] představuje počet řešení Arr [i], abychom mohli číst Arr [0] přímo po doručení, můžete získat odpověď . Rekurzivní je také velmi snadné myslet, protože když STEP změní každou změnu, předpokládá se, že lze ukázat na počet ukazatelů I, další krok může ukazovat na i-1 nebo i nebo i + 1 (bez ohledu na hranici podmínky), pak máme počet scénářů a budeme muset přidat předchozí ARR [i], abyste mohli simulovat krok za krokem.

Dále můžeme vidět kód přímo.

C++代码

Const int mod = 1e9 + 7;

Řešení třídy {

VEŘEJNÉ:

INT Numways (int Stes, int Arr_len) {

INT n = min (Arr_len, kroky / 2 + 1);

Vektor Arr (n, 0);

Arr [0] = 1;

for (int i = 0; i < kroky; ++i) {

Vektor Arr_TMP (n, 0);

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

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

Arr_TMP [J] + = Arr [i];

Arr_TMP [J] % = MOD;

}

}

Arr = Přesunout (arr_tmp);

}

Vrátit Arr [0];

}

};

Rust代码

Impl solution {

pub fn num_ways(kroky: i32, arr_len: i32) -> i32 {

Nechť n = arr_len.min (kroky + 2) / 2) jako použití;

Ať Mut Arr = VEC! [0; N];

Arr [0] = 1;

Pro i Iin 0..sts {

Nechť MUT ARR_TMP = VEC! [0; N];

Pro i v 0..n {

if arr[i] > 0 {

Pro J in (1.max (i) - 1) .. = (((N-1) .min (i + 1)) {

Arr_TMP [J] + = Arr [i];

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

}

} jinak {

Přestávka;

}

}

Arr = arr_tmp;

}

Arr [0]

}

}

Mělo by to být tady! Ne! Dnes je také speciální program na otázku, stále mám nový nápad!

Online klečícím matematickým trollem jsem dokázal, že časová složitost může dosáhnout O (kroků), ale není možné žádat o vzorec, který by dodržoval kroky = 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]

Konečná odpověď je 2188, ale ve skutečnosti si nemusíme myslet, že lze pozorovat tolik čar.

(Dodržujte koeficient, několik řádků začínajících v horní tabulce)

2188

= 1 * 835 + 1 * 1353

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

=...

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

Proto stačí vypočítat tento řádek, zeptat se na čtverec a můžete získat odpověď. (Pokud jsou kroky liché, možná budete muset počítat dva řádky, ale stále o (kroků)) a odkazuji na Yang Hui Triangle Solution Https://leetcode-cn.com/problems/pascals-triangle-ii/solution/yang -hui -san-jiao-ii-by-leetcode-solutio-shuk / je algoritmus N (N) k nalezení N-tého řádku, takže si myslím, že je to také vyřešeno, doufám, že mi pomůže vypočítat matematický troll!