/*

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
   示例 2:

输入: m = 7, n = 3
输出: 28

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

• 最简单的解法

首先本题的最简单的解法是使用排列组合，很显然，当图为m*n的时候。机器人必须要进行m-1次向右的移动操作，n-1的向下移动的操作。进行不同的排列即可。Cm+n-2 m-1。(排列组合)

• 动态规划解法

（m，n）点的路径，是（m-1，n）（m，n-1）的路径数量的和。
因此我们可以做如下代码：

//可以运行的代码

#include<iostream>
using namespace std;
int m[1000][1000] = { 0 };
int M=7, N=3;
int dx[] = { -1,0 }, dy[] = { 0,-1 };//分别代表向左移动和向上移动
int main() {for (int i = 0; i < M; i++) {m[i][0] = 1;}for (int j = 0; j < N; j++) {m[0][j] = 1;}for (int i = 1; i < M; i++) {for (int j = 1; j < N; j++) {m[i][j] = m[i + dx[0]][j + dy[0]]+m[i + dx[1]][j + dy[1]];//cout << m[i][j] <<' ';}//cout << endl;}//for (int j = 0; j < N; j++) {//	for (int i = 0; i < M; i++) {//		cout << m[i][j] << ' ';//	}//	cout << endl;
//}cout << m[M - 1][N - 1];
}

//力扣答案

class Solution {
public:int uniquePaths(int m, int n) {using namespace std;if(m==0 && n==0) return 0;int G[110][110];int dx[]={-1,0};int dy[]={0,-1};for(int i=0;i<m;i++){G[i][0]=1;}for(int j=0;j<n;j++){G[0][j]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){G[i][j]=G[i+dx[0]][j+dy[0]]+G[i+dx[1]][j+dy[1]];}}return G[m-1][n-1];}
};

在多了障碍物后，我采用了首先将记录数组m初始化成-1；然后将障碍点初始化成0，但是在行为1或者列为1的时候，我才用了都初始成1的方式，但在第二道题中，当第1行中间有一个障碍物的时候，第一行障碍物之后的数要初始化成0；我采用了一个flag实现。
//可以运行的代码

#include<iostream>
#define Temp 0
using namespace std;
int obstacleGrid[3][3] = { 0,0,0,0,1,0,0,0,0 };
int m[100][100] ;
int dx[] = { -1,0 }, dy[] = { 0,-1 };
int main() {memset(m, -1, sizeof(m)/sizeof(int));cout << m[3][5] <<"x"<< endl;int x = sizeof(obstacleGrid) / sizeof(obstacleGrid[0]);//数组的x长度int y = sizeof(obstacleGrid[0]) / sizeof(int);for (int i = 0; i < x; i++) {for (int j = 0; j < y; j++) {if (obstacleGrid[i][j] == 1) {m[i][j] = Temp;}}}if (m[0][0] == 0 || m[x - 1][y - 1] == 0) cout << 0;else {int flag = 0;for (int i = 0; i < x; i++) {if (m[i][0] == 0)flag++;if (flag != 0 && m[i][0] != Temp)m[i][0] = 0;else if (flag==0&& m[i][0] != Temp)m[i][0] = 1;}flag = 0;for (int j = 0; j < y; j++) {if (m[0][j] == 0)flag++;if (flag != 0 && m[0][j] != Temp)m[0][j] = 0;else if (flag == 0 && m[0][j] != Temp)m[0][j] = 1;}for (int i = 1; i < x; i++) {for (int j = 1; j < y; j++) {if (m[i][j] != Temp) {m[i][j] = m[i + dx[0]][j + dy[0]] + m[i + dx[1]][j + dy[1]];cout << m[i][j] << ' ';}}cout << endl;}cout << m[x - 1][y - 1];}
}

//力扣答案

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int Temp=0;
int m[1000][1000];
int dx[] = { -1,0 }, dy[] = { 0,-1 };memset(m, -1, sizeof(m)/sizeof(int));int x = obstacleGrid.size();//数组的x长度int y = obstacleGrid[0].size();for (int i = 0; i < x; i++) {for (int j = 0; j < y; j++) {if (obstacleGrid[i][j] == 1) {m[i][j] = Temp;}}}if (m[0][0] == 0 || m[x - 1][y - 1] == 0) return 0;else {int flag = 0;for (int i = 0; i < x; i++) {if (m[i][0] == 0)flag++;if (flag != 0 && m[i][0] != Temp)m[i][0] = 0;else if (flag==0&& m[i][0] != Temp)m[i][0] = 1;}flag = 0;for (int j = 0; j < y; j++) {if (m[0][j] == 0)flag++;if (flag != 0 && m[0][j] != Temp)m[0][j] = 0;else if (flag == 0 && m[0][j] != Temp)m[0][j] = 1;}for (int i = 1; i < x; i++) {for (int j = 1; j < y; j++) {if (m[i][j] != Temp) {m[i][j] = m[i + dx[0]][j + dy[0]] + m[i + dx[1]][j + dy[1]];}}}return m[x - 1][y - 1];}
}
};

代码有待优化。等我写够20题，就开始优化代码。