求解矩阵最小路径和问题。给定一个m行n列的矩阵，从左上角开始每次只能向右或者向下移动，最后到达右下角的位置，路径上的所有数字累加起来作为这条路径的路径和。编写一个实验程序求所有路径和的最小路径和，并将该路径输出。用动态规划法编写c语言代码

动态规划算法：

设 $f(i,j)$ 表示从左上角 $(1,1)$ 走到 $(i,j)$ 的所有路径中，路径和最小的那条路径的路径和。则有：

$$
f(i,j) = \min\{f(i-1,j),f(i,j-1)\} + a(i,j)
$$

其中 $a(i,j)$ 表示第 $i$ 行第 $j$ 列的元素值。

初始条件：

$$
f(1,1) = a(1,1) \\
f(1,j) = \sum_{k=1}^j a(1,k) \\
f(i,1) = \sum_{k=1}^i a(k,1)
$$

最终结果：$f(m,n)$ 就是所有路径中的最小路径和。

C 语言代码实现：

#include <stdio.h>
#include <stdlib.h>
#define M 3 // 矩阵行数
#define N 4 // 矩阵列数

int min(int a, int b) // 返回 a 和 b 中的较小值
{
    return a < b ? a : b;
}

int main()
{
    int a[M][N] = {{1, 3, 5, 9},
                   {8, 1, 3, 4},
                   {5, 0, 6, 1}};
    int f[M][N];
    int i, j;

    // 初始化
    f[0][0] = a[0][0];
    for (i = 1; i < M; i++)
        f[i][0] = f[i-1][0] + a[i][0];
    for (j = 1; j < N; j++)
        f[0][j] = f[0][j-1] + a[0][j];

    // 动态规划
    for (i = 1; i < M; i++)
        for (j = 1; j < N; j++)
            f[i][j] = min(f[i-1][j], f[i][j-1]) + a[i][j];

    // 输出最小路径和
    printf("最小路径和：%d\n", f[M-1][N-1]);

    // 输出路径
    printf("路径：");
    i = M - 1;
    j = N - 1;
    printf("(%d,%d)", i+1, j+1);
    while (i != 0 || j != 0) {
        if (i == 0)
            j--;
        else if (j == 0)
            i--;
        else if (f[i-1][j] <= f[i][j-1])
            i--;
        else
            j--;
        printf(" -> (%d,%d)", i+1, j+1);
    }
    printf("\n");

    return 0;
}