[C ++ & rust] leetcode no.1269 number of plans

题目

There is an array of length Arrlen and starts with a pointer at index 0.

In each step, you can move the pointer to the left or right, or stop in place (the pointer cannot be moved to the array range).

Give you two integers steps and arrlen, please calculate and return: After the STEPS is just executed, the pointer still points to the number of schemes at the index 0.

Since the answer may be large, please return the results of the program number 10 ^ 9 + 7.

Example 1

Enter: steps = 3, arrlen = 2

Output: 4

Explanation: After step 3, there are a total of 4 different ways to stop at indexes.

To the right, left, do not move

Do not move, right, to the left

To the right, don't move, to the left

Don't move, don't move, don't move

Example 2:

Enter: steps = 2, arrlen = 4

Output: 2

Explanation: After 2 steps, there are two different ways to stop at indexes.

To the right, to the left

Don't move, don't move

Example 3:

Enter: steps = 4, arrlen = 2

Output: 8

prompt:

1 <= steps <= 500

1 <= arrLen<= 10^6

Source: Leetcode link: https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps copyright belongs to the network all . If the business reprint, please contact the official authorization, please indicate the source of non-commercial reprint.

思路分析

This topic actually requires a little observation ability, we first see two relations between Arr and Steps. In fact, Example 2 and Example 3 show this. For Example 2, 4 lengths of ArR did not necessarily. Because a total of two steps, the up to the left is one step, it is impossible to go to the lattice behind, and we assume that there is an unlimited length of Arr and STEP equal to 5 conditions, it can be seen that up to Arr [1] The location, because once went to Arr [2], it will not come back (it has been three steps to the right, and it also needs three steps, but only 5 steps). Look at the rules

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

Therefore, we summarize a conclusion that when Arr is larger than (STEP ", there is excessive place, you can use (STEP, 2 + 1) to replace the excess Arr to achieve the purpose of reducing the calculation.

This question should be used to do, because many factors, such as this question is a simulation question, he guides us to simulate, but must timeout, you can use DFS, it will be timeout, this will guide us to think to DP, and this There is also a very critical prompt point, which we only need to get the number of scenarios, we don't need to get anything. This is also a point that the questioner considers, that is, I guides you to think so, but this is just a way of thinking, not letting you do it in this idea. This is also a suggested Iron League of DP. When the topic appears, the number of "answers", "path number", "Solution number", indicating that the topic is not every specific scheme, but the number of schemes, In this case, 99% of the case is done using DP. The amount of DP recursive is generally related to the answer to the answer, and it can even directly derive the answer itself. This que

stion is to launch an answer directly. In view of the number of scenarios to calculate, we set a DP array, Arr [i] represents the number of solutions to Arr [i], so that we can read Arr [0] directly after the delivery, you can get the answer. The recursive is also very easy to think, because when STEP changes each change, it is assumed that one can point to the I number of pointers, the next step may point to i-1 or i or i + 1 (not considering the boundary condition), then We have the number of scenarios, and we will need to add the previous ARR [i], so that you can simulate the stepped step by step.

Next we can see the code directly.

C++代码

Const int mod = 1e9 + 7;

Class solution {

PUBLIC:

INT Numways (int Stes, int Arr_len) {

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

Vector Arr (n, 0);

Arr [0] = 1;

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

Vector 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 = Move (arr_tmp);

}

Return Arr [0];

}

};

Rust代码

Impl solution {

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

Let n = arr_len.min (Steps + 2) / 2) as usize;

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

Arr [0] = 1;

For i Iin 0..sts {

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

For i in 0..n {

if arr[i] > 0 {

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

Arr_TMP [J] + = Arr [i];

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

}

} else {

Break;

}

}

Arr = arr_tmp;

}

Arr [0]

}

}

It should be over here! Not! There is also a special program today for the question, I still have a new idea!

Online kneeling a mathematical troll, I have proven that time complexity can reach O (Steps), but it is not possible to ask for the formula to observe Steps = 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]

The final answer is 2188 , but in fact, we don't have to think so many lines can be observed.

(Observe the coefficient, a few lines starting at the top table)

2188

= 1 * 835 + 1 * 1353

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

= ...

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

Therefore, you only need to calculate this line, ask the square and you can get the answer. (If Steps is odd, you may need to count two lines, but still o (steps)) and I refer to Yang Hui Triangle Solution Https://leetcode-cn.com/problems/pascals-triangle-ii/solution/yang-hui -san-jiao-ii-by-leetcode-solutio-shuk / is the algorithm of the N (N) to find the Nth line, so I think this is also solved, I hope that a mathematics troll helps me calculate !