leetcode931下降路径最小和

古城微笑少年丶 2022-09-05 11:29 52阅读 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.  和120题一样，从下往上看
2.  动态规划，观察下一层的来源，`dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+m[i][j]`注意两边的位置，来源少了，左边`dp[i][j] = min(dp[i-1][j],dp[i-1][j+1])`，右边`dp[i][j] = min(dp[i-1][j],dp[i-1][j-1])`

代码

#include<stdio.h>
    #define min(a,b) ((a)<(b)?a:b)
    int minFallingPathSum(int** matrix, int matrixSize, int* matrixColSize){ 
        int dp[matrixSize][*matrixColSize];
        int i,j;
        for(i=0;i<*matrixColSize;i++){ 
            dp[0][i] = *((int*)matrix+i);
            //printf("%d ",dp[0][i]);
        }
        printf("\n");
        for(i=1;i<matrixSize;i++){ 
            for(j=0;j<*matrixColSize;j++){ 
                if(j>=1&&j<*matrixColSize-1){ 
                    dp[i][j] = min(min(dp[i-1][j],dp[i-1][j+1]),dp[i-1][j-1])+*((int*)matrix+i*(* matrixColSize)+j);
                }
                else if(j==0){ 
                    dp[i][j] = min(dp[i-1][j],dp[i-1][j+1])+*((int*)matrix+i*(* matrixColSize)+j);
                }
                else if(j==*matrixColSize-1){ 
                    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1])+*((int*)matrix+i*(* matrixColSize)+j);
                }
            }
        }
        int minvalue = dp[matrixSize-1][0];
        for(i=0;i<*matrixColSize;i++){ 
            minvalue = min(minvalue,dp[matrixSize-1][i]);
        }
        return minvalue;
    }
    
    int main(){ 
        int m[3][3] = { { 2,1,3},{ 6,5,4},{ 7,8,9}};
        int len = 3;
        int re = minFallingPathSum((int **)m,3,&len);
        printf("re = %d\n",re);
    }

leetcode

#define min(a,b) ((a)<(b)?a:b)
    int minFallingPathSum(int** matrix, int matrixSize, int* matrixColSize){ 
        int dp[matrixSize][*matrixColSize];
        int i,j;
        for(i=0;i<*matrixColSize;i++){ 
            dp[0][i] = matrix[0][i];
            //printf("%d ",dp[0][i]);
        }
        for(i=1;i<matrixSize;i++){ 
            for(j=0;j<*matrixColSize;j++){ 
                if(j>=1&&j<*matrixColSize-1){ 
                    dp[i][j] = min(min(dp[i-1][j],dp[i-1][j+1]),dp[i-1][j-1])+matrix[i][j];
                }
                else if(j==0){ 
                    dp[i][j] = min(dp[i-1][j],dp[i-1][j+1])+matrix[i][j];
                }
                else if(j==*matrixColSize-1){ 
                    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1])+matrix[i][j];
                }
            }
        }
        int minvalue = dp[matrixSize-1][0];
        for(i=0;i<*matrixColSize;i++){ 
            minvalue = min(minvalue,dp[matrixSize-1][i]);
        }
        return minvalue;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/c4903694b3244b7c9c823a199a372722.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20220829/ef116af3d14b498599e4aa5eb308ae96.png