LintCode 1861

老鼠跳跃

题目描述

有一个老鼠从高为n的楼梯顶部跳跃下来，这个老鼠在偶数次跳跃时可以跳1, 3或者4个台阶，奇数次可以跳跃1, 2或者4个台阶。但是楼梯中间会有一些台阶上有胶水，如果跳到那些台阶上，老鼠就会被直接粘住，无法继续跳跃。你需要求出从这个楼梯顶部开始，老鼠有多少种方法能够到达地面，即第0层。若超过地面，也算是可以到达。例如从1跳跃到-1，和从1跳跃到0的方案不同。楼梯有无胶水的状态是从高往低输入的，即arr[0]为楼梯的顶部。

其中，arr[i] == 0代表当前老鼠所在的位置无胶水，arr[i] == 1代表当前老鼠所在的位置有胶水。
2<=n<=50000arr[i]=1代表台阶上有胶水，0代表没有输入保证a[0] = a[n-1] = 0答案需对1e9+7 取模
扫码免费做题

↓↓↓
样例1
输入:

[
0
,
0
,
0
]

输出:

5
解释:

楼梯总共有
3
层。

第
2
层为起点，无胶水。

第
1
层，无胶水。

第
0
层，无胶水。

老鼠的跳法为:

2
--odd(
1
)-->
1
--even(
1
)-->
0
2
--odd(
1
)-->
1
--even(
3
)-->
-2
2
--odd(
1
)-->
1
--even(
4
)-->
-3
2
--odd(
2
)-->
0
2
--odd(
4
)-->
-2
样例2
输入:

[
0
,
0
,
1
,
0
]

输出:

3
解释:

楼梯总共有
4
层。

第
3
层为起点，无胶水。

第
2
层，无胶水。

第
1
层，有胶水。

第
0
层，无胶水。

源代码

publicclassSolution
{

/**

*
@param
arr: the steps whether have glue

*
@return
: the sum of the answers

*/

privateint
MOD = 1000000007;


publicintratJump
(
int
[] arr) {

int
n = arr.length;


// state: dp[i][0] 代表从 0 的位置跳偶数步后到 i 的位置的方案数
// dp[i][1] 代表从 0 的位置跳奇数步后到 i 的位置的方案数
int
[][] dp =
newint
[n][2];


// initialization: 一开始站在 0 的位置, 已经跳过了 0 步(偶数步)
dp[0][0] = 1;


int
[] evenJumps = {1, 3, 4};

int
[] oddJumps = {1, 2, 4};


// function: dp[i][0] = dp[i - 1][1] + dp[i - 3][1] + dp[i - 4][1]
// dp[i][1] = dp[i - 1][0] + dp[i - 2][0] + dp[i - 4][0]
for
(
int
i = 1; i < n - 1; i++) {

if
(arr[i] == 1) {

continue
;

}

for
(
int
jump: evenJumps) {

if
(i - jump >= 0) {

dp[i][0] = (dp[i][0] + dp[i - jump][1]) % MOD;

}

}


for
(
int
jump: oddJumps) {

if
(i - jump >= 0) {

dp[i][1] = (dp[i][1] + dp[i - jump][0]) % MOD;

}

}

}



// answer: 研究跳到地板之前的那一步是从哪儿出发的，跳了多远
int
plans = 0;

for
(
int
jump: evenJumps) {

for
(
int
i = Math.max(0, n - jump - 1); i < n - 1; i++) {

plans = (plans + dp[i][1]) % MOD;

}

}


for
(
int
jump: oddJumps) {

for
(
int
i = Math.max(0, n - jump - 1); i < n - 1; i++) {

plans = (plans + dp[i][0]) % MOD;

}

}

return
plans;

}

}
继续阅读
阅读原文
关键词
动态
楼梯
n-1
台阶
位置