矩阵最小路径

原创

---

问题描述：

给出一个 n x m 的矩阵，从左上角开始每次只能向右走或者向下走，

最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和。

比如：

1　　3　　5　　9

8　　1　　3　　4

5　　0　　6　　1

8　　8　　4　　0

最短路径是12

解题思路：

此题属于动态规划类题目，我们可以用一个dp二维数组存放最短路径，dp[i][j]就是左上角到位置(i,j)

的最短路径，我们要求的是dp[n][m]，我们只需要从dp[i-1][j]，dp[i][j-1]这两个中选出最小者再加上

dp[n][m]自己本身的路径就可以了。

 代码：

#include<stdio.h>
#include<stdlib.h>

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

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);    //n行m列 
    
    int **arr,**dp;    //分配空间
    arr=(int **)malloc(sizeof(int *)*n);
    dp=(int **)malloc(sizeof(int *)*n);    //dp[i][j]代表从左上角到位置(i,j)时的最短距离 
    int i;
    for(i=0;i<=n-1;i++)
    { 
        arr[i]=(int *)malloc(sizeof(int)*m);
        dp[i]=(int *)malloc(sizeof(int)*m);
    } 
        
    int j;    //数组赋值 
    for(i=0;i<=n-1;i++)
        for(j=0;j<=m-1;j++)
            scanf("%d",&arr[i][j]);
            
    for(i=0;i<=n-1;i++)
        for(j=0;j<=m-1;j++)
        {
            if(i==0 && j==0)
                dp[i][j]=arr[i][j];
            if(i==0 && j!=0)    //第一行边界
                dp[i][j]=arr[i][j-1]+arr[i][j];
            if(i!=0 && j==0)    //第一列边界 
                dp[i][j]=arr[i-1][j]+arr[i][j];
            if(i!=0 && j!=0)    //其他
                dp[i][j]=arr[i][j]+min(dp[i-1][j],dp[i][j-1]);
        }    
    printf("%d",dp[n-1][m-1]);
    return 0;
} 

 2018-03-19