问题描述
'
在一个10×10大小的方格网中，从左上角开始，只能向下或者向右，走到右下角总共有多少种走法？
'
10×10大小的棋盘
1.递归
递归，就是在运行的过程中调用自己。
构成递归需具备的条件：
1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。
image.png
递归算法一般用于解决三类问题：
(1)数据的定义是按递归定义的。（Fibonacci函数）
(2)问题解法按递归算法实现。
这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。
(3)数据的结构形式是按递归定义的。
如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。
image.png
function countPaths( grid, row, col ){
if(!vaildSquare( grid, row, col )){
return 0;
}
if(isAtEnd( grid, row, col )){
return 1;
}
return countPaths( grid, row+1, col ) + countPaths( grid, row, col+1 );
}
递归的缺点：
递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
function countPaths( grid, row, col, paths ){
if(!vaildSquare( grid, row, col )){
return 0;
}
if(isAtEnd( grid, row, col )){
return 1;
}
if(paths[row][col] ==0){
paths[row][col] = countPaths( grid, row+1, col, paths ) + countPaths( grid, row, col+1, paths );
}
return paths[row][col]
}
2.动态规划
image.png
如何拆分问题，才是动态规划的核心。
image.png
image.png
2019-03-08
