c++求解矩阵最小路径和问题。给定一个m行n列的矩阵,从左上角开始每次只能向右或者向下移动,最后到达右下角的位置,路径上的所有数字累加起来作为这条路径的路径和。编写一个程序求所有路径和中的最小路径和。

下面是C++代码实现：

#include <vector>
#include <algorithm>

using namespace std;

int minPathSum(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = matrix[0][0];
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i-1][0] + matrix[i][0];
    }
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j-1] + matrix[0][j];
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j];
        }
    }
    return dp[m-1][n-1];
}

时间复杂度为 O(mn)，空间复杂度为 O(mn)。

相关问题

请用c++写一段代码：给定一个m行n列的迷宫，迷宫中每个格子中有距离数值，一个机器人只能向下和向右移动，求机器人从左上角到右下角的最短距离和最短路径

假设迷宫的距离数值矩阵为maze，m行n列，机器人从左上角出发，到达右下角的最短距离和最短路径可以使用动态规划算法解决。

具体思路如下：

1. 初始化一个m行n列的二维数组dp，用来存储每个位置到达左上角的最短距离。

2. 初始化dp[0][0]为maze[0][0]，因为机器人从左上角出发，所以到达左上角的最短距离就是左上角的距离数值。

3. 对于第一行和第一列的位置，因为只能向右或向下移动，所以到达这些位置的最短距离就是前一个位置的最短距离加上当前位置的距离数值。

4. 对于其他位置，到达当前位置的最短距离就是从上面或左边的位置中选择一个最小值，再加上当前位置的距离数值。

5. 最后dp[m-1][n-1]就是机器人从左上角到达右下角的最短距离，可以使用回溯算法找出最短路径。

代码如下：

#include <stdio.h>

#define MAX_M 100
#define MAX_N 100

int maze[MAX_M][MAX_N]; // 迷宫距离数值矩阵
int dp[MAX_M][MAX_N];   // 到达每个位置的最短距离

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

int main()
{
    int m, n;
    printf("请输入迷宫的行数和列数：");
    scanf("%d %d", &m, &n);

    printf("请输入迷宫中每个格子的距离数值：\n");
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &maze[i][j]);
        }
    }

    // 初始化dp数组
    dp[0][0] = maze[0][0];
    for (int i = 1; i < m; i++)
    {
        dp[i][0] = dp[i-1][0] + maze[i][0];
    }
    for (int j = 1; j < n; j++)
    {
        dp[0][j] = dp[0][j-1] + maze[0][j];
    }

    // 动态规划求解最短距离
    for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + maze[i][j];
        }
    }

    printf("机器人从左上角到达右下角的最短距离为：%d\n", dp[m-1][n-1]);

    // 回溯算法求解最短路径
    int x = m - 1, y = n - 1;
    while (x != 0 || y != 0)
    {
        printf("(%d,%d) ", x, y);
        if (x == 0)
        {
            y--;
        }
        else if (y == 0)
        {
            x--;
        }
        else
        {
            if (dp[x-1][y] < dp[x][y-1])
            {
                x--;
            }
            else
            {
                y--;
            }
        }
    }
    printf("(0,0)\n");

    return 0;
}

C++给定一个M行N列的矩阵，请将它调整成N行M列的矩阵（非转置）

可以先将M行N列的矩阵转化为N行M列的矩阵，再按行输出即可。

C++代码如下：

#include <iostream>
using namespace std;

int main() {
    int M, N;
    cin >> M >> N;
    int matrix[M][N];
    for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) {
            cin >> matrix[i][j];
        }
    }
    for(int j = 0; j < N; j++) {
        for(int i = 0; i < M; i++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

输入示例：

3 4
1 2 3 4
5 6 7 8
9 10 11 12

输出示例：

1 5 9 
2 6 10 
3 7 11 
4 8 12