（投资策略规划）你所掌握的算法知识帮助你从Acme计算机公司获得了一份令人兴奋的工作，签约奖金1万美元。你决定利用这笔钱进行投资，目标是10年后获得最大回报。你决定请Amalgamated投资公司管理你的投资，该公司的投资回报规则如下。该公司提供n种不同的投资，从1~n编号。在第j年,第i种投资的回报率是rij。话句话说，如果你在第j年在第i种投资投入d美元，那么在第j年年底，你会得到drij美元。回报率是有保证的，即未来10年每种投资的回报率均已知。你每年只能做出一次投资决定。在每年年底，你既可以将钱继续投入到上一年选择的投资种类中，也可以转移到其他投资中（转移到已有的投资种类，或者新的投资种类）。如果跨年时你不做投资转移，需要支付f1美元的费用，否则需要支付f2美元的费用。其中f2>f1。
a.如上所述，本问题允许你每年将钱投入到多种投资中。证明：存在最优投资策略，每年都将所有钱投入到单一投资中（记住最优投资策略只需最大化10年的回报，无需关心任何其他目标，如最小化风险）。
b.证明：规划最优投资策略问题具有最优子结构性质。
c.设计最优投资策略规划算法，分析算法时间复杂度。
d.假定Amalgamated投资公司在上述规则上又加入了新的限制条款，在任何时刻你都不能在任何单一投资种类中投入15000美元以上。证明：最大化10年回报问题不再具有最优子结构性质。
