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%，离谱
