如何计算受±1或±2步幅约束的简单路径？ [英] How to count simple paths constrained by ±1 or ±2 steps?
问题描述
我发现了这个有趣的动态编程问题，并且想知道这种方法。
我们给了一个大小为'n'的数组'a'。 / p>
数组中的每个元素均为'1'或'2'。
我们从索引 0开始。如果a [i] = 1，我们可以转到i + 1或i-1。
相反，如果a [i] = 2，我们可以转到i + 1或i + 2或i-1或i-2。
我们必须找到所有可能路径的数量。
**主要约束**：-1）我们只能一次访问数组中的特定索引。
2）我们总是从索引'0'开始。
3）路径可以在我们想要的任何时间结束：-）
示例数组：-> [1 ，1,1,1]
答案：-4
第1条可能的路径：[0]
第二种可能的路径：[0,1]
第三种可能的路径：[0,1,2]
第四个可能路径：[0,1,2,3]
另一个示例：-
[2,2,2]
答案：-5
路径：-[0]，[0,1]，[0,1,2]，[0,2,1]，[0,2]。
（此问题分为3部分！）
n的值在范围内：-1）[1,100000]
2）[1,10]
3）[1,1000]
考虑使用的空格。
0 1 2 3 4 5 6
^
为了从右边获得一个数字，必须已使用它之前的单元格。因此，以 x 结尾的所有方式都不能包含来自左侧的数字。以 x 结尾的所有方式都来自右侧，使用了 x-1 和向右移动的一组动作 x 从左侧不相交。
让 f（A，x）= l（A，x）+ r（A，x），其中 l（A，x）表示以x结尾的所有方式左边; r（A，x），从右边开始。
要获得 l（ A，x），我们需要：
（1）所有到达途径（x-1 ）
= l（A，x-1）
（x右边没有数字用于
，并且由于
x最后使用，所以我们可以不是
从右边到达x-1。）
（2）所有到达（x-2）的方式：
显然我们需要l（A，x-2 ）。现在
将从右边到达（x-2），
唯一有效的路径是
...（x-3）->（x-1）-> （x-2）
等于
从左侧到达（x-3）的路数。
= l（A，x-2）+ l（A，x-3）
要获得 r（A，x），我们需要：
（1）所有到达（x + 1）的方式，因此
直接从那里到达x
= l（A，x-1）
（我们只能从（x-1）到达（x + 1）。）
（2）从（x + 1）开始在
之后到达（x + 2）的所有方式
= l（A，x-1）* f（A [x + 1 ...]，1）
（到达
A [ x + 1 ...]，我们必须先到达
（x-1）。）
所以看来
f（A，x）= l（A，x）+ r（A，x ）
l（A，x）=
l（A，x-1）+ l（A，x-2）+ l（A，x-3）
r（A，x）=
l（A，x-1）+ l（A，x-1）* f（A [x + 1 ...]，1）
下面的JavaScript代码每次运行时都会尝试使用不同的7元素数组。我将备忘录和优化留给读者使用（为了有效地制表 f（_，1），请注意 l（_，1）= 1 ）。
function f（A，x）{ if（x< 0 || x> A.length-1）返回0返回l（A，x）+ r（A，x）函数l（A，x）{if（x< 0 || x > A.length-1）如果（x == 0）则返回0，如果（A [x-2]&& A [x-2] ==，则返回1 let结果= 1（A，x-1） 2）{结果+ = l（A，x-2）如果（A [x-3]&& A [x-3] == 2）结果+ = l（A，x-3）}返回结果}函数r（A，x）{如果（x< 0 || x> = A.length-1 ||！（A [x-1]&& A [x-1] == 2） ）如果（（A [x + 2]&& A [x + 2] == 2）结果+ = l（A，x-1）* f（ A.slice（x + 1），1）返回结果}}函数validate（A）{令n = A.length函数g（i，s）{如果（调试）console.log（s）let result = 1 let [a，b] = [i + 1，i-1]如果（< n&& ！s.includes（a））结果+ = g（a，s.slice（）。concat（a））如果（b> = 0&&！s.includes（b））结果+ = g（ b，s.slice（）。concat（b））如果（A [i] == 2）{[a，b] = [i + 2，i-2]如果（a< n&！ s.includes（a））结果+ = g（a，s.slice（）。concat（a））如果（b> = 0&&！s.includes（b））结果+ = g（b ，s.slice（）。concat（b））}返回结果}返回g（0，[0]）}让debug = falselet arr = []让n = 7for（让i = 0； i
I have found this interesting dynamic-programming problem and want to know the approach .
We are given an array 'a' of size-'n'.
Each element of the array is either '1' or '2'.
We start at index '0' . If a[i]=1 , we can go to i+1 or i-1.
On the contrary, If a[i]=2 , we can go to i+1 or i+2 or i-1 or i-2.
We have to find the number of all possible paths .
**Main Constraint ** : - 1) We can go to a particular index in an array only once .
2) We always start at the index-'0' .
3) A path can end anytime we want :- )
Example array : --> [1,1,1,1]
Answer : - 4
1ST possible path : [0]
2ND possible path : [0,1]
3rd possible path : [0,1,2]
4th possible path : [0,1,2,3]
Another example : -
[2,2,2]
Answer:- 5
Paths : - [0],[0,1],[0,1,2] , [0,2,1] , [0,2] .
(This question is divided into-3-parts!)
Value(s) of n are in range : - 1) [1,100000]
2) [1,10]
3)[1,1000]
Consider used spaces.
0 1 2 3 4 5 6
^
In order to reach a number from the right, the cell just before it must have been used. Therefore, all the ways to end with x coming from the left cannot include numbers from the right. And all the ways to end with x coming from the right used x-1 and a set of moves to the right of x disjoint from the left side.
Let f(A, x) = l(A, x) + r(A, x), where l(A, x) represents all ways to end at x coming from the left; r(A, x), coming from the right.
To obtain l(A, x), we need:
(1) all ways to reach (x-1)
= l(A, x-1)
(there are no numbers used to
the right of x, and since
x is used last, we could not
have reached x-1 from the right.)
(2) all ways to reach (x-2):
cleary we need l(A, x-2). Now
to reach (x-2) from the right,
the only valid path would have
been ...(x-3)->(x-1)->(x-2)
which equals the number of ways
to reach (x-3) from the left.
= l(A, x-2) + l(A, x-3)
To obtain r(A, x), we need:
(1) all ways to reach (x+1) so as
to directly go from there to x
= l(A, x-1)
(We can only reach (x+1) from (x-1).)
(2) all ways to reach (x+2) after
starting at (x+1)
= l(A, x-1) * f(A[x+1...], 1)
(To get to the starting point in
A[x+1...], we must first get to
(x-1).)
So it seems that
f(A, x) = l(A, x) + r(A, x)
l(A, x) =
l(A, x-1) + l(A, x-2) + l(A, x-3)
r(A, x) =
l(A, x-1) + l(A, x-1) * f(A[x+1...], 1)
The JavaScript code below tries a different 7-element array each time we run it. I leave memoisation and optimisation to the reader (for efficiently tabling f(_, 1), notice that l(_, 1) = 1).
function f(A, x){
if (x < 0 || x > A.length - 1)
return 0
return l(A, x) + r(A, x)
function l(A, x){
if (x < 0 || x > A.length - 1)
return 0
if (x == 0)
return 1
let result = l(A, x-1)
if (A[x-2] && A[x-2] == 2){
result += l(A, x-2)
if (A[x-3] && A[x-3] == 2)
result += l(A, x-3)
}
return result
}
function r(A, x){
if (x < 0 || x >= A.length - 1 || !(A[x-1] && A[x-1] == 2))
return 0
let result = l(A, x-1)
if (A[x+2] && A[x+2] == 2)
result += l(A, x-1) * f(A.slice(x+1), 1)
return result
}
}
function validate(A){
let n = A.length
function g(i, s){
if (debug)
console.log(s)
let result = 1
let [a, b] = [i+1, i-1]
if (a < n && !s.includes(a))
result += g(a, s.slice().concat(a))
if (b >= 0 && !s.includes(b))
result += g(b, s.slice().concat(b))
if (A[i] == 2){
[a, b] = [i+2, i-2]
if (a < n && !s.includes(a))
result += g(a, s.slice().concat(a))
if (b >= 0 && !s.includes(b))
result += g(b, s.slice().concat(b))
}
return result
}
return g(0, [0])
}
let debug = false
let arr = []
let n = 7
for (let i=0; i<n; i++)
arr[i] = Math.ceil(Math.random() * 2)
console.log(JSON.stringify(arr))
console.log('')
let res = 0
for (let x=0; x<arr.length; x++){
let c = f(arr, x)
if (debug)
console.log([x, c])
res += c
}
if (debug)
console.log('')
let v = validate(arr)
if (debug)
console.log('')
console.log(v)
console.log(res)
这篇关于如何计算受±1或±2步幅约束的简单路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
