动态规划-二维费用问题——879.盈利计划

1.题目解析

 题目来源

879.盈利计划——力扣

 测试用例

2.算法原理 

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

i下标从小到大即可，j与k下标不用特殊要求

5.返回值 

返回最后一个位置的dp值，即dp[group.size()][n][minProfit]

3.实战代码

class Solution {
public:
    int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) 
    {
        const int MOD = 1e9 + 7;
        int len = p.size();
        vector<vector<vector<int>>> dp(len+1
        ,vector<vector<int>>(n+1,vector<int>(m+1)));
        
        for(int j = 0;j <= n;j++)
        {
            dp[0][j][0] = 1;
        }
        for(int i = 1;i <= len;i++)
        {
            for(int j = 0;j <= n;j++)
            {
                for(int k = 0;k <= m;k++)
                {
                    dp[i][j][k] += dp[i-1][j][k];
                    if(j >= g[i-1])
                    {
                        dp[i][j][k] += dp[i-1][j-g[i-1]][max(0,k-p[i-1])];
                    }
                    dp[i][j][k] %= MOD;
                }
            }
        }
        return dp[len][n][m];
    }
};

代码解析 

4.代码优化（dp表降维）