首页 > 4.24 京东笔试
头像
_helloworld__
编辑于 2021-04-25 14:23
+ 关注

4.24 京东笔试 投票

第一题就是求众数 投票法a掉
第二题抽卡序列 动规解
题目描述:
初始位置0已有卡片0,现在有1~n的卡片,从卡牌中随机抽一张出来加入末尾,求满足下面条件的卡牌序列有多少种
1、最末尾位置为卡片n
2、相邻两位置卡片数字的差值绝对值大小不超过2

输入 3
输出 2
解释: 有2个合法的序列 {0,1,2,3}、{0,2,1,3}
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[1] = 1; 
        dp[2] = 1; 
        dp[3] = 2; 

        int MOD = 998244353;

        for(int i = 4;i < n + 1;i++){
            dp[i] = (dp[i-1] + dp[i-3])%MOD;
        }
        System.out.println(dp[n]);

    }
}
简单说下我的思路,以i结尾的序列可以由i-1、i-3计算到
i-1非常直观 直接在dp[i-1]的每个序列后 添加一个i就可以
但是这种添加的方法实际上限定了最后两个位置分别是i-1,i

实际上最后2个位置还可以是i-2,i
所以在dp[i-3]的所有序列后面固定添加{i-1,i-2,i}的序列也是解

即dp[i] = dp[i-1]+dp[i-3]

全部评论

(13) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐