动态规划就是自底向上的过程，它是知道底部每一步的值是多少，然后一步步递推。特别是对于二维动态规划，其实就是从表中一步步往上推。
动态规划的无后效性：就是我下一个状态是由当前状态推出来的，但是并不关心当前状态怎么来的。而且我后面状态的计算依赖当前状态，但是不会改变当前状态。
假设你拥有一根长度为n的钢条，你可以切割成任意长度并出售，不同长度的钢条有不同的价格。你需要找到一种切割方式，使得总的收益最大化。
在这个问题中，如果我们已经知道切割到某一长度i时的最大收益，那么无论这根钢条是如何被一步步切割到长度i的（即不管之前切割的具体位置和顺序），继续进行最优切割的决策时，我们只需要考虑当前长度i的收益情况，而不需要关心它是如何从原始长度一步步被切割至此的。也就是说，对于长度i，其最优解只取决于长度为i+1到n的钢条切割后的收益，与之前是如何切割到长度i无关。这就是动态规划中的无后效性体现。
例如，如果已知切割长度为3时的最大收益是10元，那么无论之前是先切成了1+2还是直接切成了3，当我们考虑下一步切割时，只要依据这个长度3的最优收益去决策即可，不必回顾之前的切割细节。这样，我们可以逐步构建出从长度1到长度n的最优解，每个状态的决策都是独立且最优的，体现了无后效性的原则。
问题1：开始有一头母牛，母牛每年会生一只母牛，新出生的母牛成长三年后也能每年生一只母牛，假设牛都不会死。 求N年后，母牛的数量。
public class cow {
public int cowNum(int n){
if(n <= 0)
return 0;
if(n == 1 || n == 2 || n == 3)
return n;
return cowNum(n - 1) + cowNum(n - 3);
}
public static void main(String[] args) {
System.out.println(new cow().cowNum( 4));;
}
}
问题2：打印一个字符串的全部子序列，包括空字符串
public class printAllSubsequence {
public void printAll(char[] arr, int i, String res){
if(i == arr.length){
System.out.println(res);
return;
}
printAll(arr, i + 1, res + arr[i]);
printAll(arr, i + 1, res);
}
public static void main(String[] args) {
String res = "abc";
new printAllSubsequence().printAll(res.toCharArray(), 0, "");
}
}
问题3：给你一个二维数组，二维数组中的每个数都是正数，要求从左上角走到右下角，每一步只能向右或者向下。沿途经过的数字要累加起来。返回最小的路径和。
public class minPath {
public int minPath(int[][] matrix, int i, int j){
int res = matrix[i][j];
if(i == matrix.length - 1 && j == matrix[0].length - 1)
return res;
if(i == matrix.length - 1)
return res + minPath(matrix, i, j + 1);
if(j == matrix[0].length - 1)
return res + minPath(matrix, i + 1, j);
int right = minPath(matrix, i, j + 1);
int down = minPath(matrix, i + 1, j);
return res + Math.min(right, down);
}
public static void main(String[] args) {
int[][] m = { { 1, 3, 5, 9 }, { 8, 1, 3, 4 }, { 5, 0, 6, 1 }, { 8, 8, 4, 0 } };
System.out.println(new minPath().minPath(m, 0, 0));
}
}
问题4：给你一个数组arr，和一个整数aim。如果可以任意选择arr中的数字，能不能累加得到aim。能返回true，否则为false。
public class isSum {
public boolean isSum(int[] arr, int i, int sum, int aim){
if(i == arr.length)
return sum == aim;
return isSum(arr, i + 1, sum, aim) || isSum(arr, i + 1, sum + arr[i], aim);
}
public static void main(String[] args) {
int[] arr = {1, 4, 8};
System.out.println(new isSum().isSum(arr, 0, 0, 12));
}
}
