9.9递归和动态规划（一）——小孩上楼梯的方式的种类

	//递归法
	/**
	 * 思路：自上而下的方式。
	 * 最后一步可能是从第n-1阶往上走1阶、从第n-2阶往上走2阶或从第n-3阶往上走3阶。
	 * 因此，抵达最后一阶的走法，抵达这最后三阶的方式的综合。
	 * @param n
	 * @return
	 */
	public static int countWays(int n){
		if(n<0)
			return 0;
		else if(n==0)//注意此处条件
			return 1;
		else{
			return countWays(n-1)+countWays(n-2)+countWays(n-3);
		}
	}

	//动态规划
	/**
	 * 思路：每次调用都会分支出三次调用。予以动态规划加以修正。
	 * @param n
	 * @param map
	 * @return
	 */
	public static int countWaysDP(int n,int[] map){
		if(n<0)
			return 0;
		else if(n==0)
			return 1;
		else if(map[n]>-1)
			return map[n];
		else{
			map[n]=countWaysDP(n-1,map)+countWaysDP(n-2,map)+countWaysDP(n-3, map);
			return map[n];
		}
	}

版权声明：本文为博主原创文章，未经博主允许不得转载。