首先说一个剪枝的概念：
剪枝出现在递归和类递归程序里，因为递归操作用图来表示就是一棵树，树有很多分叉，如果不作处理，就有很多重复分叉，会降低效率，如果能把这些分叉先行记录下来，就可以大大提升效率——这就是剪枝技巧。他的做法和动规很像（将状态保存起来，用空间换时间），就是在递归的过程中把出现的状态存储下来
具体见代码：
source code（跳台阶）：
package niuke;
public class 跳台阶 {
public static int Solution1(int i,int n){
if(i > n) return 0;
//the step number is more than the whole step,
// it isn't a correct result, so return the 0
if(i == n) return 1;
//the step number is equal with the whole steps
//so return 1
return Solution1(i+1,n) + Solution1(i+2,n);
}
public static int Solution2(int i,int n,int[] memo){//which cut the branches unnecessary
if(i > n) return 0;
if(i == n) return 1;
if(memo[i] > 0) return memo[i];
memo[i] = Solution2(i + 1,n,memo) + Solution2(i + 2,n,memo);
return memo[i];
}
}
source code（变态跳台阶）：
package niuke;
public class 变态跳台阶 {
private static int Solution1(int i, int n) {//simulate _brute-force method
if (i > n) return 0;
if (i == n) return 1;
int sum = 0;
for (int j = 1; j < n; ++j) {
sum += Solution1(i + j, n);
}
return sum;
}
private static int Solution2(int i, int n, int[] memo) {
if (i > n) return 0;
if (i == n) return 1;
if (memo[i] > 0) return memo[i];
for (int j = 1; j <= n; ++j) {
memo[i] += Solution2(i + j, n, memo);
}
return memo[i];
}
}
Solution2均使用了剪枝技巧
代码已经ac
希望对大家有所帮助
以上