A robot is located at the top-left corner of amxngrid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note:mandnwill be at most 100.
Array Dynamic Programming
最开始见到这道题，一眼就感觉这是高中很简单的组合问题。
总共需要走m+n-2步，其中横着需要走n-1步，竖着需要走m-1。所以总共的组合有
或者
种，这两个值是相同的。
但是编写代码是最开始没有考虑整数会溢出。32位的int表示的最大的整数为10位，这对于计算上面的组合是远远不够的。考虑m=32,n=14，就需要计算32*31*……*19。这个结果已经出了int型的表示范围，即使使用long long型，它也只能表示大约20位整数。这对于上面m，n最多为100而言是远远不够的。这种情况下就需要使用double类型了。double类型能表示的数字可以有300多位。
在这个过程中发现了C++中<limits>中已经包含了一个类模板，可以用它来求解各种数据类型的最大值和最小值。这个类模板中还有其它的静态函数，这里就不介绍了，需要查看与类型相关的限制了，可以在这个类模板中寻找答案。如下：
#include <iostream>#include <vector>#include <limits>using namespace std;int main(){//numeric_limits：这是一个类模板，max是这个类模板中的静态成员函数cout<<"unsigned long long max :"<<numeric_limits<unsigned long long>::max()<<endl;cout<<"unsigned long long min :"<<numeric_limits<unsigned long long>::min()<<endl;cout<<"long long max :"<<numeric_limits< long long>::max()<<endl;cout<<"long long min :"<<numeric_limits< long long>::min()<<endl;cout<<"long max :"<<numeric_limits<long>::max()<<endl;cout<<"long min :"<<numeric_limits<long>::min()<<endl;cout<<"int max :"<<numeric_limits<int>::max()<<endl;cout<<"int min :"<<numeric_limits<int>::min()<<endl;cout<<"unsigned int max :"<<numeric_limits<unsigned int>::max()<<endl;cout<<"unsigned int min :"<<numeric_limits<unsigned int>::min()<<endl;cout<<"float max :"<<numeric_limits<float>::max()<<endl;cout<<"float min :"<<numeric_limits<float>::min()<<endl;cout<<"double max :"<<numeric_limits<double>::max()<<endl;cout<<"double min :"<<numeric_limits<double>::min()<<endl;return 0;}结果：
而且由于上面两个组合在数学上的计算结果是相等的，所以如果m<n，那么可以用
，，如果m>n，那么可以用
，这样可以减少运算量。
最后代码终于执行通过了。
runtime:0ms
class Solution {public:int uniquePaths(int m, int n) {if(m==1||n==1) return 1;int A=max(m,n);int B=min(m,n);double result=1;//double可以表示300多位，int可以表示10位，float可以表示38位for(int i=A;i<=A+B-2;i++){result*=i;}for(int i=1;i<=B-1;i++){result/=i;}return int(result);}};不过这道题的本意其实是使用动态规划来求解，从下面的标签中提示Dynamic Programming中可以看出。
使用动态规划也很简单，因为到每一个格子只能从它的左边格子或上边格子到达，动态规划的数学公式就已经推到出来了。这里的一个技巧就是将数组的宽和高都增加1，这样就不需要处理边界情况了。编码时又碰到的一个小技巧就是动态数组的初始化，结果翻开C++ Primer发现里面也有讲解。
runtime:0ms
class Solution {public:int uniquePaths(int m, int n) {int **arr=new int*[m+1]();for(int i=0;i<=m;i++)arr[i]=new int[n+1]();//动态分配的数组后面加上()表示需要编译器对数组做初始化，但是这种方式只能使用该类型的缺省值，即不能自己指定初始值arr[1][1]=1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(!(i==1&&j==1))arr[i][j]=arr[i-1][j]+arr[i][j-1];}}return arr[m][n];}};
放下一种执着，收获一种自在。放下既是一种理性抉择，也是一种豁达美。
