3054: 最低通行费 来看看吧 DP和DFS两种做法

解题思路:             两种做法不知道你更喜欢哪一种，本人更喜欢DFS 哈哈哈哈哈

注意事项:

参考代码:

DP做法

#include"bits/stdc++.h"
using namespace std;
// 定义全局变量n和二维数组a、dp
int n, a[110][110], dp[110][110];
int main() {
    // 读取矩阵的大小n
    cin >> n;
    // 读取矩阵a的元素
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    // 初始化dp数组的起点
    dp[1][1] = a[1][1];
    // 初始化第一行和第一列的dp值
    for (int i = 2; i <= n; i++) {
        dp[1][i] = dp[1][i - 1] + a[1][i]; // 第一行的dp值累加
        dp[i][1] = dp[i - 1][1] + a[i][1]; // 第一列的dp值累加
    }
    // 动态规划计算其他位置的dp值
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            // 当前位置的dp值为从左边或上边到达的最小值加上当前位置的值
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + a[i][j];
        }
    }
    // 输出右下角的dp值，即从左上角到右下角的最小费用
    cout << dp[n][n];
    return 0;
}

DFS做法

#include"bits/stdc++.h"
using namespace std;
// 定义全局变量n和二维数组a、kkk、vis
int n, a[110][110];
int kkk[110][110];
bool vis[110][110];
void dfs(int x, int y, int t) {
    // 如果当前路径和大于已记录的最小路径和，则返回
    if (t > kkk[x][y]) {
        return;
    }
    // 更新当前点的最小路径和
    kkk[x][y] = t;
    // 遍历两个方向：向下和向右
    for (int i = 1; i <= 2; i++) {
        // 如果可以向下移动且未访问过该点
        if (!vis[x + 1][y] && i == 1) {
            // 标记该点为已访问
            vis[x + 1][y] = 1;
            // 递归调用dfs，向下移动一步
            dfs(x + 1, y, t + a[x + 1][y]);
            // 回溯，取消标记
            vis[x + 1][y] = 0;
        }
        // 如果可以向右移动且未访问过该点
        if (!vis[x][y + 1] && i == 2) {
            // 标记该点为已访问
            vis[x][y + 1] = 1;
            // 递归调用dfs，向右移动一步
            dfs(x, y + 1, t + a[x][y + 1]);
            // 回溯，取消标记
            vis[x][y + 1] = 0;
        }
    }
}
int main() {
    // 输入矩阵的大小n
    cin >> n;
    // 输入矩阵的值并初始化kkk数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            kkk[i][j] = 99999; // 初始化为一个较大的值
        }
    }
    // 从起点(1,1)开始进行深度优先搜索
    dfs(1, 1, 0);
    // 输出从起点到终点的最小费用和加上起点的费用
    cout << kkk[n][n] + a[1][1] << endl;
    return 0;
}