NC553 又见台阶(四种语言+视频讲解)

- 题目描述：

- 题目链接：
https://www.nowcoder.com/practice/fac4dc5774204806b7f07ac9e00fb073?tpId=196&&tqId=37241&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking

- 设计思想：

详细操作流程看下图:

-视频讲解链接B站视频讲解
- 复杂度分析：

- 代码：
c++版本:

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
        //dp[i]代表跳到第i级台阶的方法数
        /*
        如果台阶i有水不能跳 dp[i] = 0;
        他可以跳奇数层台阶，所以对于i为奇数的时候，它一定是从i为偶数的地方跳过来
        dp[奇数] = Sum(dp[偶数])
        对于i为偶数的时候，它一定是从i为奇数的地方跳过来
        */
        int mod = 1e9 + 7;
        int cnt = 0;//用于遍历数组a
        vector<int> dp(n + 1, 0); //dp[i]表示i级台阶方法数
        dp[0] = 1;
        int odd = 0;//i为奇数的时候dp[i]的总和
        int even = 1;//i为偶数的时候dp[i]的总和，对于i=2他只能有一种跳格子方案
        for(int i = 1;i <= n;i ++){
            if(cnt<m && i == a[cnt]){
                cnt ++;
            }else{
                if(i % 2 == 0){
                    dp[i] = odd % mod;
                    even = (even+dp[i])%mod;
                }else{
                    dp[i] = even % mod;
                    odd = (odd + dp[i])%mod;
                }
            }
        }
        return dp[n];
    }
};

Java版本：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int m, int[] a) {
        // write code here
        int mod = (int)1e9 + 7;
        int cnt = 0;//用于遍历数组a
        int[] dp=new int[n+1];//dp[i]表示i级台阶方法数
        dp[0] = 1;
        int odd = 0;//i为奇数的时候dp[i]的总和
        int even = 1;//i为偶数的时候dp[i]的总和，对于i=2他只能有一种跳格子方案
        for(int i = 1;i <= n;i ++){
            if(cnt < m && i == a[cnt]){
                cnt ++;
            }else{
                if(i % 2 == 0){
                    dp[i] = odd % mod;
                    even = (even+dp[i])%mod;
                }else{
                    dp[i] = even % mod;
                    odd = (odd + dp[i])%mod;
                }
            }
        }
        return dp[n];
    }
}

Python版本:

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @param m int整型 
# @param a int整型一维数组 
# @return int整型
#
class Solution:
    def solve(self , n , m , a ):
        # write code here
        mod = 10 ** 9 + 7
        cnt = 0#用于遍历数组a
        dp = [0] * (n + 1)#dp[i]表示i级台阶方法数
        dp[0] = 1;
        odd = 0#i为奇数的时候dp[i]的总和
        even = 1#i为偶数的时候dp[i]的总和，对于i=2他只能有一种跳格子方案
        for i in range(1,n+1):
            if cnt < m and i == a[cnt]:
                cnt += 1
            else:
                if i % 2 == 0:
                    dp[i] = odd % mod;
                    even = (even+dp[i])%mod;
                else:
                    dp[i] = even % mod;
                    odd = (odd + dp[i])%mod;
        return dp[n]

JavaScript版本:

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @param a int整型一维数组 
 * @return int整型
 */
function solve( n ,  m ,  a ) {
    // write code here
        let mod = 1e9 + 7;
        let cnt = 0;//用于遍历数组a
        let dp = [0];//dp[i]表示i级台阶方法数
        dp[0] = 1;
        let odd = 0;//i为奇数的时候dp[i]的总和
        let even = 1;//i为偶数的时候dp[i]的总和，对于i=2他只能有一种跳格子方案
        for(let i = 1;i <= n;i ++){
            dp[i] = 0;
            if(cnt < m && i == a[cnt]){
                cnt ++;
            }else{
                if(i % 2 == 0){
                    dp[i] = odd % mod;
                    even = (even+dp[i])%mod;
                }else{
                    dp[i] = even % mod;
                    odd = (odd + dp[i])%mod;
                }
            }
        }
        return dp[n];
}
module.exports = {
    solve : solve
};