过到是过了……1900+ms……弱了
先说下自己做法 按背包模型DP 滚动数组……f[i][j]表示需要f[i][j]-1个面值为a[i]的银币才可凑成价格j,f[i][j]=0即不可凑成
优化了一下j的范围 1~limit_j;limit_j=min{m,max+a[i]*c[i]} max代表用前面的硬币能凑到的最大值
初始f[0][0]=1;max=0;
若f[i-1][j]>0,f[i][j]=1;
若f[i-1][j]=0,检查f[i][j-a[i]](j-a[i]>=0)是否>0且<=c[i],成立则f[i][j]=f[i][j-a[i]]+1并同时检查max是否需要更新

请大牛指导一下更快的方法……