golang刷leetcode动态规划之如何解决盈利计划问题

1.题目要求是统计利润至少为 P，且人数最多为 G 的方案数。由于利润最多有可能达到 100 * n，数据范围过大而不方便进行动态规划，可以考虑该问题的对偶问题。即统计人数最多为 G 的方案数，减去利润小于 P，且统计人数最多为 G 的方案数。2.对于第一部分，动态规划的状态为 s(i,j)，表示考虑了前 i 个计划，参与人数为 j 的方案数是多少。对于第 i 个计划，s(i,j)=s(i,j)+s(i−1,j−group[i])。初始值 s(0,0)=1。人数最多为 G 的方案数为 ∑Gj=0s(n,j)。实际上可以省略掉第一维。3,对于第二部分，动态规划的状态为 f(i,j,k)，表示考虑了前 i 个计划，参与人数为 j 的方案数，且利润为 k 的方案数是多少。对于第 i 个计划，f(i,j,k)=f(i,j,k)+f(i−1,j−group[i],k−profit[i])。初始值 f(0,0,0)=1。利润小于 P，且统计人数最多为 G 的方案数为 ∑j<=G,k<Pj=k=0f(n,j,k)。实际上可以仍然省略掉第一维。4.最终答案就是两部分做差。5.为了防止中间结果溢出，每次计算都要取摸6.由于取摸了，所以结果可能是负值，所以要加摸

func profitableSchemes(G int, P int, group []int, profit []int) int {    mod := 1000000007    n:=len(group)    s:=make([]int,G+1)    s[0]=1    for i:=0;i<n;i++{        for j:=G;j>=group[i];j--{           //s[i,j]=s[i,j]+s[i-1,j-group[i]]             s[j]=(s[j]+s[j-group[i]])%mod        }    }    f:=make([][]int,G+1)    for i:=0;i<=G;i++{        f[i]=make([]int,P+1)    }    f[0][0]=1        for i:=0;i<n;i++{        for j:=G;j>=group[i];j--{            for k:=P-1;k>=profit[i];k--{                //f[i,j,k]=f[i,j,k]+f[i-1,j-group[i],k-profit[i]]                f[j][k]=(f[j][k]+f[j-group[i]][k-profit[i]])%mod            }        }    }          ss:=0    for j:=0;j<=G;j++{        ss=(ss+s[j])%mod    }        ff:=0    for j:=0;j<=G;j++{        for k:=0;k<P;k++{            ff=(ff+f[j][k])%mod           }    }    return (ss-ff+mod)%mod}