UniquePath
这里两道题目，虽然只有一点差别，但是前者可以用一个组合数直接算出，后面则需要DP。
先看第一道，似乎是之前编程之美看过的Catalan数那题的一道课后习题，也是问从二维空间坐上到右下之类的，
最多有多少unique条路径，一开始我以为是n-1 里面插入m-1个位置，然后加上n-1个数两端n个插入m-1个位置，
然后以为是C(n,m-1)，如果大的话反过来，后来发现错了，这样会漏掉m-1个数连续放在一起的情况，因为未必每个都单独占一个坑，
所以还是统一起来看，n-1+m-1个位置里选n-1(m-1), 不考虑顺序的，因为选定之后，只有一种排列，因此是组合数。但是测了发现OJ有个错误，
其实当n=m=100, 到最大范围时已经超了int的范围，如果用double每次乘以一个比例的话最后精度会丢导致结果出错，但是似乎最大198连乘到100似乎超过了
最大的范围了，包括unsigned long long, long double 都超了，所以即使不要求返回int，似乎需要bitset来处理乘积嘛。
class Solution {
public:
int uniquePaths(int m, int n) {
//double product=1;
unsigned long long up=1,down=1;
if(n>m) swap(n,m);
for(int i=n-1;i>=1;i--)
{
up*=(unsigned long long)(m-1+i);
down*=(unsigned long long)(i);
}
unsigned long long a=up/down;
return (int)a;
//product*=(double(m-1+i)/(i));//:i=n-1->1
//return (int)product;
}
};
第二道放了障碍，简单的DP，但是甩了几脚，当上和左都不是障碍时，我把条件与了，其实如果分别一个是的话，也是可以算的，所以这里没有仔细考虑算法，还有就是DP都是1…m 1..n这个是经验，
然后数据都从0开始，因此DP基本都要和数据下表相差1，数据要-1 包括ij
class Solution {
public:
int dp[200][200];
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int m=obstacleGrid.size();
if(m==0) return 0;
int n=obstacleGrid[0].size();
if(n==0) return 0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=0;
if(obstacleGrid[i-1][j-1]==1) continue;
if(i>=2 && j>=2)
{
if(obstacleGrid[i-2][j-1]==0)
dp[i][j]+=dp[i-1][j];
if(obstacleGrid[i-1][j-2]==0)
dp[i][j]+=dp[i][j-1];
}
else if(i==1 && j>=2 && obstacleGrid[i-1][j-2]==0)
dp[i][j]=dp[i][j-1];
else if(i>=2 && j==1 && obstacleGrid[i-2][j-1]==0)
dp[i][j]=dp[i-1][j];
else if(i==1 && j==1)
dp[i][j]=1;
}
}
/*
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
cout<<dp[i][j]<<" ";
cout<<endl;
}*/
return dp[m][n];
}
};
不优化反而变成了WA了，一直以为有什么边界没处理，结果是空间没优化，最后200MB内存，01背包还是要空间优化