Xiao Ming want to run up a staircase with n steps. When he on the ith step, he can go up one to num[i] steps. How many ways can Ming run up the stairs? Since the answer may be very large, just output the answer module 1e9+7.
1 <= n <= 10^6
1 <= num[i] <=10^6
At first, Ming was at the 0th step and he needed to go to the nth step.
Give n=3,num=[3,2,1] , return 4
Explanation:
Option 1: Take 3 steps up at the 0th step
Option 2: Take 1 step up at the 0th step,and take 2 steps up at the 1st step
Option 3: Take 1 step up at the 0th step,and take 1 step up at the 1st step,then take 1 step up at the 2rd step
Option 4: Take 2 steps up at the 0th step,and take 1 step up at the 2rd step
Give n=4,num=[1,1,1,1],return 1
Explanation:
Mr Wang can only take 1 step at a time, so there is only one solution.
package l1553;
public class Solution {
/**
* @param n: the number of steps
* @param num: the maximum step Ming can run up at the ith step
* @return: Return the number of ways to run up the stairs
*/
public long Solve(int n, int[] a) {
// Write your code here
long[]dp=new long[n+1];
dp[0]=1;
for(int i=0;i<n;i++) {
for(int j=1;j<=a[i];j++) {
if(i+j>n) break;
dp[i+j]+=dp[i];
dp[i+j]%=1000000007;
}
}
return dp[n];
}
}
直接DP会TLE，然后想考虑状压DP，但是i位置不行，不代表i之前的位置不行
然后就想考虑2个边缘的信息，但是只考虑2个边缘不够的
需要换个思路：
原来naive的DP数组dp[i]表示：到位置为i的所有方法数，而在计算dp数组有个明显累加的过程，我们可以在左边的时候用正数，右边用负数，这样DP数组的含义就变化了，sum(dp[0:i])表示到i位置可行的方法数
