golang刷leetcode动态规划（8）盈利计划

帮派里有 G 名成员，他们可能犯下各种各样的罪行。

第 i 种犯罪会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。

让我们把这些犯罪的任何子集称为盈利计划，该计划至少产生 P 的利润。

有多少种方案可以选择？因为答案很大，所以返回它模 10^9 + 7 的值。

示例 1：

输入：G = 5, P = 3, group = [2,2], profit = [2,3]

输出：2

解释：

至少产生 3 的利润，该帮派可以犯下罪 0 和罪 1 ，或仅犯下罪 1 。

总的来说，有两种方案。

示例 2:

输入：G = 10, P = 5, group = [2,3,5], profit = [6,7,8]

输出：7

解释：

至少产生 5 的利润，只要他们犯其中一种罪就行，所以该帮派可以犯下任何罪行 。

有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

提示：

1 <= G <= 100

0 <= P <= 100

1 <= group[i] <= 100

0 <= profit[i] <= 100

1 <= group.length = profit.length <= 100

解题思路：

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
}

复制