我发现了这个有趣的动态编程问题，并且想知道这种方法。
我们给了一个大小为'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步幅约束的简单路径？
发布评论