首页 > 试题广场 >

又见台阶

[编程题]又见台阶

热度指数：1322 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

台阶一共有 ${n}$ 层，有一些台阶上有积水。

牛牛一开始在第0层，它每次可以跳奇数层台阶，他想跳到第n层，但是它不希望在跳跃的过程中踩到积水。

已知有 ${m}$ 个台阶上有积水。
请问牛牛在不踩到积水的情况下跳到第n层有多少种不同的方案。如果不可能到达第 ${n}$ 层，则答案为0。

为了防止答案过大，答案对1e9+7取模。

示例1

输入

9,3,[1,3,5]

输出

说明

因为1，3，5都不能走，所以第一步可以跳到第7层或者第9层
所以一共两种方案：
1. 第一步跳7，第二步跳1，第三步跳1
2. 第一步跳9

备注:



第一个参数代表台阶的阶数
第二个参数m代表有多少层台阶有积水
第三个参数vector a包含m个数字，每个数字代表第层台阶有积水。保证没有重复元素且以升序给出。

算法知识视频讲解

萨巴鲁酱

class Solution {
public:
    /**
     * 又见台阶
     * @param n int整型 
     * @param m int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, int m, vector<int>& a) {
        // write code here
        const int MOD = 1e9 + 7;
        vector<int> dp(n+1, 0);
        dp[0] = 1;
        //分别表示奇数台阶和偶数台阶的方法数的前缀和，在初始状态下因为有dp[0] = 1，所以evenSum = 1
        int oddSum = 0, evenSum = 1;
        int idx = 0; // 记录当前遍历到的a数组的下标
        for(int i = 1; i <= n; ++i){
            // 这个if语句用于跳过a数组中的台阶，即积水台阶
            if(i == a[idx]){
                idx++;
                continue;
            }
            // 如果当前台阶是奇数，则只能由之前的偶数台阶跳上来
            if(i & 1){
                // 更新到达当前台阶的方法数
                dp[i] = (dp[i] + evenSum) % MOD;
                // 利用dp[i]更新奇数台阶的总方法数
                oddSum = (oddSum + dp[i]) % MOD;
            }
            // 如果当前台阶是偶数，则只能由之前的奇数台阶跳上来
            else{
                dp[i] = (dp[i] + oddSum) % MOD;
                evenSum = (evenSum + dp[i]) % MOD;
            }   
        }
        return dp[n];
    }
};

编辑于 2020-05-19 14:23:37 回复(0)

hpp1905

1. 最开始用动态规划，想的是 dp[i] 表示跳到第i层的方案数。但是遍历的时候发现 dp[i] 是由i之前的所有能够跳奇数个台阶加和而来的。所以里面有一个内层循环，所有能够跳的位置的方案数都要加起来，导致超时。

2. 假设 dp[i] 是i层之前的能够跳到第i层的方案数的和，这样是为了避免了内层循环。为了求dp[i]，我们要找出来那些位置能够跳到i层。可以发现，当i是奇数时，可以从偶数位置跳过来（跳奇数个台阶）；当i是偶数时，可以从奇数位置跳过来。所以为了求dp[i]，我们只用记录下来 i层之前的奇数位置的方案数的和以及偶数位置的方案数的和。然后dp[i] 的值可以加在奇数位置或偶数位置方案数的和里面，为下一个dp[i+1]做准备。

int solve(int n, int m, vector<int>& a) {
        // write code here
        const int mod = 1000000007;
        int odd_sum = 0; // 前面奇数层位置的方案数的和
        int even_sum = 1; // 前面偶数层位置的方案数的和，位置0作为偶数
        int water_index = 0; // 有水台阶的索引
        for (int i = 1; i < n; i++) { // 最后一层先不跳
            // 如果当前有水台阶层数小于 i， 那么一直向后走。是为了判断i层是否有水
            while (water_index < a.size() && a[water_index] < i) { // 
                water_index++;
            }
            if (water_index >= a.size() || i != a[water_index]) {  // i层没水
                if (i % 2 == 1) { // i层是奇数。
                    odd_sum = (odd_sum + even_sum) % mod; // i层之前的奇数层方案数 + 第i层方案数。第i层方案数是从偶数层跳奇数个台阶而来。
                } else {
                    even_sum = (even_sum + odd_sum) % mod; // i层之前的偶数层方案数 + 第i层方案数。第i层方案数是从奇数层跳奇数个台阶而来。
                }
            }
        }
        if (a.back() == n) {
            return 0;
        } else {
            return ((n % 2 == 1) ? even_sum : odd_sum); // 最后一层是奇数，则从偶数层跳过来。是偶数，则从奇数层跳过来。
        }
    }

发表于 2020-04-29 09:51:48 回复(0)

7777gloryglory

这道题是动态规划问题，和斐波那契不同的是我们不是利用上两次的值，而是为奇数和&偶数和。

奇数和 = 上一次奇数和 + 上一次的偶数和；

偶数和 = 上一次偶数和 + 上一次的奇数和；

当遇到水沟这一层时，不管这层是奇数或者是偶数，都不会更新对应的奇数和&偶数和。

以本题给示例为例： 9层， 1，3，5层为水沟。

初始化奇数和 sum1 = 0, 偶数和sum2 = 1;

n = 1; 奇数层，但是由于是水沟，不更新sum1

n = 2; 偶数层，更新sum2 = sum2 + sum1 = 1 + 0 = 1；

n = 3；奇数层，水沟层，不更新sum1

n = 4; 偶数层， sum2 = sum2 + sum1 = 1 + 0 = 1; （sum1 还为 0哦，奇数层还没被更新过）

n = 5; 奇数层，水沟层，不更新sum1

n = 6, 偶数层， sum2 = sum2 + sum1 = 1 + 0 = 1;

n = 7, 奇数层， sum1 = sum1 + sum2 = 0 + 1 = 1；

n = 8, 偶数层， sum2 = sum2 + sum1 = 1 + 1 = 2；

n = 9, 奇数层， sum1 = sum1 + sum2 = 1 + 2 = 3；

最终n为奇数，输出偶数和

n为偶数，输出奇数和， 9为奇数，输出sum2 = 2。

其次我们需要判断水沟层是否在n层，如果是直接返回0。

class Solution {
public:
    /**
     * 又见台阶
     * @param n int整型 
     * @param m int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, int m, vector<int>& a) {
        // write code here
        
        const int MOD = 1e9 + 7;
        
        int first = 0;         //奇数
        int second = 1;        //偶数
        int water_idx = 0;
        
        for(int i = 1; i <= n; i++) {
            
            if(a[water_idx] == i) {
                water_idx++;
                continue;
            }
            
            if(i % 2 == 0) {
                //偶数
                second = second + first;
                second %= MOD;
            }
            else {
                //奇数
                first = first + second;
                first %= MOD;
            }   
        }
        
        if(a.back() == n) {   
            return 0;
        }
        return n % 2 == 0 ? first : second;
    }
};

发表于 2020-08-05 22:00:57 回复(0)

牛客771280939号

import java.util.*;


public class Solution {
    /**
     * 又见台阶
     * @param n int整型 
     * @param m int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    int MAX=1000000007;
    public int solve (int n, int m, int[] a) {
        // write code here;
        int[] dp=new int[n+1];
        for(int i:a){
            dp[i]=-1;
        }
        int[] pre= new int[n+1];//前缀和
        for(int i=0;i<=n;i++){
            if(dp[i]<0){
               dp[i]=0;
            }else{
                if(i%2==0){
                    //如果是偶数，
                  dp[i]=i>=1?pre[i-1]:0;
                  dp[i]=dp[i]%MAX;          
                }else{
                    dp[i]=i>=1?pre[i-1]:0;
                    dp[i]=dp[i]%MAX;
                    dp[i]=dp[i]+1;
                }
            }
            pre[i]=(i>=2?pre[i-2]:0)+dp[i];
            pre[i]=pre[i]%MAX;
            //preJ
        }
        return dp[n];
    }
   
}

dp+前缀和

发表于 2020-04-22 02:05:05 回复(2)