牛客网——剑指offer(跳台阶以及变态跳台阶_java实现)

首先说一个剪枝的概念:

剪枝出现在递归和类递归程序里,因为递归操作用图来表示就是一棵树,树有很多分叉,如果不作处理,就有很多重复分叉,会降低效率,如果能把这些分叉先行记录下来,就可以大大提升效率——这就是剪枝技巧。他的做法和动规很像(将状态保存起来,用空间换时间),就是在递归的过程中把出现的状态存储下来

具体见代码:

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

希望对大家有所帮助

以上

上一篇:java中annotation


下一篇:Linux I/O优化 磁盘读写参数设置