每日一练之unique-paths

1. unique-paths

OJ地址：unique-paths

【方法】动态规划

int uniquePaths(int m, int n) {// write code hereint res[m][n];//初始化for(int i = 0; i < m; i++){res[i][0] = 1;}for(int j = 0; j < n; j++){res[0][j] = 1;}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++)//状态转移方程res[i][j] = res[i][j-1] + res[i-1][j];}return res[m-1][n-1];}

2. unique-paths II

OJ地址：unique-paths II

【方法】：动态规划

int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {// write code hereint m = obstacleGrid.size();int n = obstacleGrid[0].size();if(m == 0)return 0;vector<vector<int>> f(m, vector<int>(n, 0));for(int i = 0; i < m; i++){if(obstacleGrid[i][0] == 1)break;f[i][0] = 1;}for(int j = 0; j < n; j++){if(obstacleGrid[0][j] == 1)break;f[0][j] = 1;}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(obstacleGrid[i][j] == 1)f[i][j] = 0;elsef[i][j] = f[i-1][j] + f[i][j-1];}}return f[m-1][n-1];}

3. minimum-path-sum

OJ地址：minimum-path-sum

int minPathSum(vector<vector<int> >& grid) {// write code hereint m = grid.size();int n = grid[0].size();if(m == 0)return 0;vector<vector<int>> f(m, vector<int>(n, 0));f[0][0] = grid[0][0];for(int i = 1; i < m; i++)f[i][0] = f[i-1][0] + grid[i][0];for(int j = 1; j < n; j++)f[0][j] = f[0][j-1] + grid[0][j];for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i][j];}}return f[m-1][n-1];}