动态规划
动态规划与 分治策略 很类似，都是将一个原问题分解为若干规模较小的子问题，递归的解决这些子问题，然后合并子问题的解得到原问题的解
两者区别在于，分治策略解决的问题中，各个子问题通常是相互独立的，但是动态规划中的各个子问题通常是有重叠的，当针对一个子问题的解求出后，可以将其记忆化储存
之前有讲过 动态规划之背包问题 ，这里是另一个比较经典的问题——挖金矿
挖金矿问题与分析
5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同；参与挖矿的工人总数是10人；每座金矿要么全挖，要么不挖，不能派一半人挖一半金矿；若要尽可能多地挖取金矿，则怎么选择金矿？
金矿1： 200金/3人
金矿2： 300金/4人
金矿3： 350金/3人
金矿4： 400金/5人
金矿5： 500金/5人
为了理清思路，可以先先之前 动态规划之背包问题 中的分析一样，做出动态规划的表格，其中的具体分析都可以参考背包问题中的分析
- 考虑只有一个金矿时，工人数从1个到10个的递增过程中，可以获得的黄金的数量
- 考虑只有两个金矿时，工人数从1个到10个的递增过程中，可以获得的黄金的数量
- 考虑只有三个金矿时，工人数从1个到10个的递增过程中，可以获得的黄金的数量
- 考虑只有四个金矿时，工人数从1个到10个的递增过程中，可以获得的黄金的数量
- 考虑具有五个金矿时，工人数从1个到10个的递增过程中，可以获得的黄金的数量
当人数不足以挖金矿时，只能获得 0 黄金，也是动态规划的边界
当人数只能够挖一座金矿时，选择最大黄金数的金矿
当人数足够挖两个金矿时，选择是挖一座黄金量多的黄金，还是挖两座黄金量少的黄金
以此类推
示例代码
Python
def get_gold(golds, ores, num_man):
num_ore = len(ores)
# 为了方便计算，多开辟了一行、一列
dp = [[0 for i in range(num_man+1)] for _ in range(num_ore+1)]
for i in range(1, num_ore+1):
for j in range(1, num_man+1):
if j < ores[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-ores[i-1]] + golds[i-1])
return dp[num_ore][num_man]
golds = [200, 300, 350, 400, 500]
ores = [3, 4, 3, 5, 5]
num_man = 10
ans = get_gold(golds, ores, num_man)
Java
public class GoldMain {
public static void main(String[] args) {
int[] golds = {200, 300, 350, 400, 500};
int[] ores = {3, 4, 3, 5, 5};
int manNum = 10;
int result = getGold(golds, ores, manNum);
System.out.println(result);
}
// golds 表示金矿含金量，ores 表示挖矿需要人数，manNUm 表示总人数
public static int getGold(int[] golds, int[] ores, int manNum) {
int oLen = ores.length;
// dp[i][j] 表示有 oLen 个金矿，manNum 人数时可以获得黄金量
int[][] dp = new int[oLen + 1][manNum + 1];
for (int i = 1; i < oLen+1; i++) {
for (int j = 1; j < manNum+1; j++) {
if (j < ores[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-ores[i-1]] + golds[i-1]);
}
}
}
return dp[oLen][manNum];
}
}
