leetcode 64.最小路径和（minimum path sum）c语言

1.description

https://leetcode-cn.com/problems/minimum-path-sum/description/

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入: [ [1,3,1], ⁠ [1,5,1], ⁠ [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。

2.solution

回溯法加备忘录在倒数第2个case超时了

void solve(int i, int j, int dist, int gridSize, int gridColSize, int **grid, int *p, int **mem){
          
   
    if(i==gridSize-1 && j==gridColSize || i==gridSize && j==gridColSize-1){
          
   
        if(dist < *p){
          
   
            *p = dist;
        }
        return;
    }

    if(i<gridSize && j<gridColSize){
          
   
        if(dist+grid[i][j] > mem[i][j]) return;
        mem[i][j] = dist+grid[i][j];
        solve(i+1, j, dist+grid[i][j], gridSize, gridColSize, grid, p, mem); //向下移动
        solve(i, j+1, dist+grid[i][j], gridSize, gridColSize, grid, p, mem); //向右移动
    }
}

int minPathSum(int** grid, int gridSize, int* gridColSize){
          
   
    int mind = INT_MAX; // 最短路径
    int *p = &mind; // 用于修改mind

    int **mem = (int**)malloc(gridSize*sizeof(int*));
    for(int i=0; i<gridSize; ++i){
          
   
        mem[i] = (int*)malloc((*gridColSize)*sizeof(int));
        memset(mem[i], 127, (*gridColSize)*sizeof(int));
    }

    solve(0, 0, 0, gridSize, *gridColSize, grid, p, mem);

    return mind;
}

换用动态规划：

#define min(a,b) (((a) < (b)) ? (a) : (b))

int minPathSum(int** grid, int gridSize, int* gridColSize){
          
   
    int **dp = (int**)malloc(gridSize*sizeof(int*));
    for(int i=0; i<gridSize; ++i){
          
   
        dp[i] = (int*)malloc(*gridColSize*sizeof(int));
    }

    int sum = 0;
    // 初始化dp第一行
    for(int i=0; i<*gridColSize; ++i){
          
   
        sum += grid[0][i];
        dp[0][i] = sum;
    }
    sum = 0;
    // 初始化dp第一列
    for(int i=0; i<gridSize; ++i){
          
   
        sum += grid[i][0];
        dp[i][0] = sum;
    }

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

    int res = dp[gridSize-1][*gridColSize-1];

    // free
    for(int i=0; i<gridSize; ++i){
          
   
        if(dp[i]){
          
   
            free(dp[i]);
        }
    }

    if(dp){
          
   
        free(dp);
    }

    return res;
}

将二维的状态表压缩成二维的vector

#define min(a,b) (((a) < (b)) ? (a) : (b))

static inline void swap(int **p, int **q){
          
   
    int *tmp = *p;
    *p = *q;
    *q = tmp;
}

int minPathSum(int** grid, int gridSize, int* gridColSize){
          
   
    int *pre = (int*)malloc(*gridColSize*sizeof(int));
    int *cur = (int*)malloc(*gridColSize*sizeof(int));

    pre[0] = grid[0][0];
    for(int i=1; i<*gridColSize; ++i){
          
   
        pre[i] = pre[i-1] + grid[0][i];
    }

    for(int i=1; i<gridSize; ++i){
          
   
        cur[0] = pre[0] + grid[i][0];
        for(int j=1; j<*gridColSize; ++j){
          
   
            cur[j] = grid[i][j] + min(pre[j], cur[j-1]);
        }
        swap(&pre, &cur);
    }
 
    int res = pre[*gridColSize-1];
    
    // free
    if(pre){
          
   
        free(pre);
    }

    if(cur){
          
   
        free(cur);
    }
    
    return res;
}

进一步压缩到一维vector

#define min(a,b) (((a) < (b)) ? (a) : (b))

int minPathSum(int** grid, int gridSize, int* gridColSize){
          
   
    // 将二维的状态表压缩成了一维的vector
    int *dp = (int*)malloc(*gridColSize*sizeof(int));

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

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

    int res = dp[*gridColSize-1];
    
    if(dp){
          
   
        free(dp);
    }
    
    return res;
}