问题

给出个投资项目，每个项目有种投资方式
第个项目第种投资方式需要花的钱，最后会得到的钱
现在你有共有总量为的钱，合理分配，最终最多能赚多少钱

解析

令表示前个项目共花费元能够得到的最大价值
则选择第个第种投资方式能得到的最大价值应该是
证明:的任意一个确定状态的子决策都是此状态下的最优决策

• 已知是前个项目共花费元能够得到的最大价值
• 假设子决策不是这种状态下能得到的最大价值
• 那么一定存在另一个子决策
• 用这个子决策替换原来的子决策，必然可以得到一个更大的,这与之前的假设想冲突，因此不存在这个一个
• 得证

设计

for (int i = 1; i <= n; ++i)
    {
        for (int j = m; j >= 0; --j)
        {
            for (int k = 0; j - k >= 0 && k <= o; ++k)
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + f[i][k]);
            }
        }
    }

分析

一共三层循环，第一层n次，第二层m次，第三层o次
总复杂度

源码

传送门