当前位置：首页 > article >正文

【每日一题】04最小路径和（DP3）

article 2024/9/20 23:35:48

问题描述

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

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

示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

问题求解

使用f[i][j]表示到位置[i][j]的最短路径长度
初始条件: f[0][0] = grid[0][0]
状态转移方程： f[i][j] = fmin(f[i-1][j] , f[i][j-1]) + grid[i][j]
边界条件:第一列 j=0: f[i][j] = f[i-1][j] + grid[i][j]; 第一行 i=0: f[i][j] = f[i][j-1] + grid[i][j];

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

    f[0][0] = grid[0][0];

    int i,j,temp;
    for(i=0; i<gridSize; i++){
        for(j = 0; j<gridColSize[0]; j++){
            if(i>0 && j >0){
                temp = fmin(f[i-1][j], f[i][j-1]);
                f[i][j] = temp + grid[i][j];
            }
            else if(i > 0){
                f[i][j] = f[i-1][j] + grid[i][j];
            }
            else if(j >0){
                f[i][j] = f[i][j-1] + grid[i][j];
            }
        }
    }

    return f[gridSize-1][gridColSize[0]-1];
    
}