leetcode--62不同路径和64.最小路径和（C语言）

1、62.不同路径

2、两种解法

1、递归法（代码简洁，效率不高）

可以画出一棵树，叶子节点个数对应路径个数。

void  path(int m, int n,int *p){
    if(m==0 && n==0)
        (*p)++;
    if(m>0)
        path(m-1,n,p);
    if(n>0)
        path(m,n-1,p);
}


int uniquePaths(int m, int n){
    int a = 0;
    path(m-1,n-1,&a);
    return a;
}
           

2、动态规划

假设 dp[i][j] 表示到达（i,j）的路径的个数。那么就有

dp[j][i] = dp[j-1][i] + dp[j][i-1];

int uniquePaths(int m, int n){
    int dp[n][m];
    int i, j;
    for(i=0; i<m; i++)
        dp[0][i] = 1;
        
    for(j=1; j<n; j++)
        dp[j][0] = 1;
        
    for(i=1; i<m; i++)
        for(j=1; j<n; j++)
            dp[j][i] = dp[j-1][i]+dp[j][i-1];
    return dp[n-1][m-1];
}
           

3、64.最小路径和

和62题的思路大同小异，也是利用动态规划。

int min(int a, int b){
    return a<b?a:b;
}

int minPathSum(int** grid, int gridSize, int* gridColSize){
    int dp[gridSize][*gridColSize];
    int i,j;

    dp[0][0] = grid[0][0];

    for(i=1; i<(*gridColSize); i++)
        dp[0][i] = dp[0][i-1]+grid[0][i];
    for(i=1; i<gridSize; i++)
        dp[i][0] = dp[i-1][0]+grid[i][0];

    for(i=1; i<gridSize; i++)
        for(j=1; j<(*gridColSize); j++)
            dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
    return dp[gridSize-1][*gridColSize-1];
}