[C ++ & rust] leetcode no.1269 suunnitelmien määrä

题目

On olemassa Arrlen-pituinen taulukko, joka alkaa osoittimella indeksistä 0.

Jokaisessa vaiheessa voit siirtää osoitinta vasemmalle tai oikealle tai pysähtyä paikalleen (osoitinta ei voi siirtää taulukkoalueelle).

Anna sinulle kaksi kokonaislukua ja arrlen, laske ja palauta: Kun STEPS on juuri suoritettu, osoitin osoittaa edelleen kaavioiden määrää indeksissä 0.

Koska vastaus voi olla suuri, palauta ohjelman numero 10 ^ 9 + 7 tulokset.

Esimerkki 1

Syötä: vaiheet = 3, arrlen = 2

Tulos: 4

Selitys: Vaiheen 3 jälkeen on yhteensä 4 eri tapaa pysähtyä indekseihin.

Oikealle, vasemmalle, älä liiku

Älä liiku oikealle, vasemmalle

Oikealle, älä liiku, vasemmalle

Älä liiku, älä liiku, älä liiku

Esimerkki 2:

Syötä: vaiheet = 2, arrlen = 4

Tuloste: 2

Selitys: Kahden vaiheen jälkeen on kaksi eri tapaa pysähtyä indekseihin.

Oikealle, vasemmalle

Älä liiku, älä liiku

Esimerkki 3:

Syötä: vaiheet = 4, arrlen = 2

Tulos: 8

kehote:

1 <= askelta <= 500

1 <= arrLen<= 10^6

Lähde: Leetcode-linkki: https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps tekijänoikeus kuuluu verkostolle kaikille . Jos yritys uusintapainos, ota yhteyttä viralliseen valtuutukseen, ilmoita lähde ei-kaupallinen uusintapainos.

思路分析

Tämä aihe vaatii itse asiassa hieman havainnointikykyä, näemme ensin kaksi suhdetta Arrin ja Stepsin välillä. Itse asiassa esimerkki 2 ja esimerkki 3 osoittavat tämän. Esimerkissä 2 ArR:n 4 pituutta eivät välttämättä. Koska yhteensä kaksi askelta, ylös vasemmalle on yksi askel, takana olevaan hilaan on mahdotonta mennä, ja oletetaan, että Arr ja STEP on rajattomasti pituudeltaan yhtä suuri kuin 5 ehtoa, voidaan nähdä, että ylös to Arr [1] Sijainti, koska kerran mennyt Arriin [2], se ei tule takaisin (se on ollut kolme askelta oikealle, ja se tarvitsee myös kolme askelta, mutta vain 5 askelta). Katso säännöt

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

Tästä syystä teemme yhteenvedon johtopäätöksestä, että kun Arr on suurempi kuin (STEP ", paikkaa on liikaa, voit käyttää (STEP, 2 + 1) korvaamaan ylimääräisen Arr laskennan pienentämiseksi.

Tätä kysymystä tulisi käyttää, koska monet tekijät, kuten tämä kysymys on simulaatiokysymys, hän opastaa meitä simuloimaan, mutta täytyy aikakatkaista, voit käyttää DFS:ää, se on aikakatkaisu, tämä ohjaa meidät ajattelemaan DP:lle, ja tämä On myös erittäin kriittinen kehotekohta, jonka tarvitsee vain saada skenaarioiden määrä, meidän ei tarvitse saada mitään. Tämä on myös seikka, jonka kysyjä pohtii, eli ohjaan sinua ajattelemaan niin, mutta tämä on vain tapa ajatella, ei anna sinun tehdä sitä tässä ajatuksessa. Tämä on myös ehdotettu Iron League of DP. Kun aihe tulee näkyviin, "vastausten", "polun numero", "ratkaisun numero" määrä, mikä osoittaa, että aihe ei ole jokainen tietty kaavio, vaan skeemojen lukumäärä, Tässä tapauksessa 99% tapauksesta tehdään käyttämällä DP. DP-rekursiivisen määrä liittyy yleensä vastaukseen vastaukseen, ja se voi jopa johtaa itse vastauksen suoraan. Tämä que

tehtävänä on aloittaa vastaus suoraan. Laskettavien skenaarioiden lukumäärän vuoksi asetimme DP-taulukon, Arr [i] edustaa Arr [i]:n ratkaisujen määrää, jotta voimme lukea Arr [0] heti toimituksen jälkeen, saat vastauksen . Rekursiivia on myös erittäin helppo ajatella, koska kun STEP muuttaa jokaista muutosta, oletetaan, että voidaan osoittaa I määrää osoittimia, seuraava askel voi osoittaa i-1 tai i tai i + 1 (rajaa huomioimatta). ehto), meillä on skenaarioiden määrä, ja meidän on lisättävä edellinen ARR [i], jotta voit simuloida vaiheittaista vaihetta.

Seuraavaksi näemme koodin suoraan.

C++代码

Const int mod = 1e9 + 7;

Luokan ratkaisu {

JULKINEN:

INT Numways (int Stes, int Arr_len) {

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

Vektori Arr (n, 0);

Arr [0] = 1;

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

Vektori 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 = Siirrä (arr_tmp);

}

Palautin [0];

}

};

Rust代码

Impl solution {

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

Olkoon n = arr_len.min (Vaiheet + 2) / 2) käyttöarvona;

Anna Mut Arr = VEC! [0; N];

Arr [0] = 1;

I Iin 0..sts {

Annetaan MUT ARR_TMP = VEC! [0; N];

I in 0..n {

jos arr[i] > 0 {

J:lle (1.max (i) - 1) .. = (((N-1) .min (i + 1)) {

Arr_TMP [J] + = Arr [i];

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

}

} muu {

Tauko;

}

}

Arr = arr_tmp;

}

Läh. [0]

}

}

Sen pitäisi olla täällä! Ei! Tänään on myös erikoisohjelma kysymykselle, minulla on vielä uusi idea!

Olen verkossa polvillaan matemaattista peikkoa osoittanut, että aikamonimutkaisuus voi saavuttaa O:n (askeleen), mutta ei ole mahdollista pyytää kaavaa noudattamaan vaiheita = 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]

Lopullinen vastaus on 2188 , mutta itse asiassa meidän ei tarvitse ajatella, että niin monta viivaa voidaan havaita.

(Tarkista kerrointa, muutama rivi alkaen ylätaulukosta)

2188

= 1 * 835 + 1 * 1353

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

=...

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

Siksi sinun tarvitsee vain laskea tämä viiva, kysyä neliötä ja saat vastauksen. (Jos Steps on pariton, saatat joutua laskemaan kaksi riviä, mutta silti o (askeleita)) ja viittaan Yang Huin kolmioratkaisuun Https://leetcode-cn.com/problems/pascals-triangle-ii/solution/yang -hui -san-jiao-ii-by-leetcode-solutio-shuk / on N:n (N) algoritmi N:nnen rivin löytämiseksi, joten mielestäni tämäkin on ratkaistu, toivon, että matematiikan peikko auttaa minua laskemaan !