如题,问答+前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) 回帖