leetcode64最小路径和

秒速五厘米 2022-09-05 04:05 110阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]

思路

1.  从(0,0)开始，向左向下都只有一种方法能到达，所以`dp[i][0] = dp[i-1][0]+nums[i][0];dp[0][j]=dp[0][j-1]+nums[0][j]`
2.  其他部分`dp[i][j] = min(dp[i-1][j],dp[i][j-1])+nums[i][j]`;

代码

#include<stdio.h>
    #include<string.h>
    #define min(a,b) ((a)<(b)?a:b)
    int minPathSum(int** grid, int gridSize, int* gridColSize){ 
        int dp[gridSize][*gridColSize];
        memset(dp,0,sizeof(dp));
        dp[0][0] = *((int *)grid);
        int i,j;
        for(i=0;i<gridSize;i++){ 
            for(j=0;j<*gridColSize;j++){ 
                if(i==0&&j>0){ 
                    dp[i][j] = dp[i][j-1]+*((int *)grid+i*(*gridColSize)+j);
                }
                else if(j==0&&i>0){ 
                    dp[i][j] = dp[i-1][j]+*((int *)grid+i*(*gridColSize)+j);
                }
                else if(j>0&&i>0){ 
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1])+*((int *)grid+i*(*gridColSize)+j);
                }
            }
        }
        return dp[gridSize-1][*gridColSize-1];
    }
    
    int main(){ 
        int a[3][3] = { { 1,3,1},{ 1,5,1},{ 4,2,1}};
        int len = 3;
        int re = minPathSum(a,3,&len);
        printf("re = %d \n",re);
    }

leecode

#define min(a,b) ((a)<(b)?a:b)
    int minPathSum(int** grid, int gridSize, int* gridColSize){ 
        int dp[gridSize][*gridColSize];
        memset(dp,0,sizeof(dp));
        dp[0][0] = grid[0][0];
        int i,j;
        for(i=0;i<gridSize;i++){ 
            for(j=0;j<*gridColSize;j++){ 
                if(i==0&&j>0){ 
                    dp[i][j] = dp[i][j-1]+grid[i][j];
                }
                else if(j==0&&i>0){ 
                    dp[i][j] = dp[i-1][j]+grid[i][j];;
                }
                else if(j>0&&i>0){ 
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j];;
                }
            }
        }
        return dp[gridSize-1][*gridColSize-1];
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/9c72e5b053814a48a443f72c8de94a8f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20220829/cab1b1dfd87b409c85f554e090d1c4f9.png