While writing a recursive solution to the problem https://codeforces.com/contest/1389/problem/B I didn't take count (which is the number of steps taken till now) into account in the dp states. But now that I think of it ,I wonder why doesn't the dp(recursion) depend on the no of steps left.
Here is the link to my submission :https://codeforces.com/contest/1389/submission/122378801. Here idx represents the present index we are currently in, check denotes whether the last move was left(1) or right(0) and mleft is count of moves to the left we have taken so far. Can anyone help me understand why is it independent on the no of steps taken/left.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/18/2024 00:50:00 (l2).
Desktop version, switch to mobile version.
Supported by
Have you seen the editorial at https://codeforces.com/blog/entry/80809? I haven't read over your code but from the editorial you can see that DP isn't even needed for this problem.