动态规划（二）
例：给你一个数组arr，和一个整数aim。如果可以任意选择arr中的数字，能不能累加得到aim，返回true或者false。
测试数据：
int[] arr = { 1, 4, 8 };
int aim = 12;
1.写出尝试（递归）版本
private static boolean isSum1(int[] arr, int i, int sum, int aim) {
if (i == arr.length) {
return sum == aim;
}
return isSum1(arr, i + 1, sum, aim) || isSum1(arr, i + 1, sum + arr[i], aim);
} 2.分析可变参数，哪几个可变参数的值能代表返回状态，几个可变参数，就构造几维表。
数组和aim不可变，i,sum可变，本题为后效性问题。
3.看base case，列出不依赖的位置。
二维表行代表sum,列代表i。
| I \ SUM | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 0 | |||||||||||||
| 1 | |||||||||||||
| 2 | |||||||||||||
| 3 | F | F | F | F | F | F | F | F | F | F | F | F | T |
4.分析一个普遍位置的依赖。
return isSum1(arr, i + 1, sum, aim) || isSum1(arr, i + 1, sum + arr[i], aim); 要知道一个普遍位置的值，就得知道它的下一行的值和下一行，向右加arr[i]列的值。
最后一列和最后一行知道了，反过来就能填完了整张表。
| i \sum | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 0(arr[0]=1) | T | F | F | T | T | F | F | T | T | F | F | T | T |
| 1(arr[1]=4) | T | F | F | F | T | F | F | F | T | F | F | F | T |
| 2(arr[2]=8) | F | F | F | F | T | F | F | F | F | F | F | F | T |
| 3 | F | F | F | F | F | F | F | F | F | F | F | F | T |
动态规划代码为：
private static boolean isSum2(int[] arr, int aim) {
boolean[][] dp = new boolean[arr.length + 1][aim + 1];
for (int i = 0; i < dp.length; i++) {
dp[i][aim] = true;
}
for (int i = arr.length - 1; i >= 0; i--) {
for (int j = aim - 1; j >= 0; j--) {
dp[i][j] = dp[i + 1][j];
if (j + arr[i] <= aim) {
dp[i][j] = dp[i][j] || dp[i + 1][j + arr[i]];
}
}
}
// for (int i = 0; i < arr.length + 1; i++) {
// for (int j = 0; j < aim + 1; j++) {
// System.out.print(dp[i][j] + "\t");
// }
// System.out.println("");
// }
return dp[0][0];
}
