首页 > 8.26腾讯音乐笔试第三题求解
头像
Darreni
编辑于 2021-08-26 22:41
+ 关注

8.26腾讯音乐笔试第三题求解


如题,问答+前2道编程就花了我30分钟,最后一道DP了1个小时还是只能过60%,然后就超时了离谱😫😫
我的代码:
        public int FillArray (int[] a, int k) {
            // write code here
            int mod = (int)(Math.pow(10, 9)+7);
            int n =a.length;
            //dp[i][j]表示第i个数选择j的方案数
            int[][] dp = new int[n][k+1];
            if(a[0]!=0){
                dp[0][a[0]]=1;
            }else{
                for(int i=1;i<=k;i++){
                    dp[0][i] = 1;
                }
            }

            for(int i=1;i<n;i++){
                if(a[i]!=0){
                    for(int j=0;j<=a[i];j++){
                        dp[i][a[i]] = (dp[i][a[i]]%mod + dp[i-1][j]%mod)%mod;
                    }
                }else{
                    for(int j=0;j<=k;j++){
                        for(int x=0;x<=j;x++){
                            dp[i][j] = (dp[i][j]%mod + dp[i-1][x]%mod)%mod;
                        }
                    }
                }
            }

            int ans = 0;
            if(a[n-1]!=0){
                ans = dp[n-1][a[n-1]];
            }else{
                for(int i=0;i<=k;i++){
                    ans = (ans%mod+dp[n-1][i]%mod)%mod;
                }
            }
            return ans;
        }

状态压缩后,还是只能60%,离谱

全部评论

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

相关热帖

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

近期精华帖

热门推荐