贪心算法机器人收集硬币

Question

贪心算法解决了收集硬币的问题
棋盘上有一定数量的硬币。机器人从左上角开始，走到右下角。机器人只能向两个方向移动:向右和向下。机器人一边走一边收集硬币。想要使用最少数量的机器人收集所有的硬币，要求是需要一个C++代码

我弄出来的代码结果是八，不知道哪里出问题了

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题分析： 这是一个典型的动态规划问题。因为机器人只能向右或向下移动，所以到达图中的某个位置只有两种可能：从上面的位置移动过来或从左边的位置移动过来。所以我们可以定义一个二维数组dp，其中dp[i][j]表示机器人从左上角走到(i,j)位置时收集硬币的最小数量。那么 dp[i][j] 可以通过上一步的状态，也就是 dp[i-1][j] 和 dp[i][j-1] 转移过来。即 dp[i][j] = min(dp[i-1][j], dp[i][j-1])+coins[i][j]。 贪心算法似乎并不能很好地解决这个问题。 以下是详细解答和C++代码实现：

1. 定义一个二维数组dp，并初始化dp[0][0] = coins[0][0]（左上角位置的硬币数量）。
2. 然后，分别处理第一行和第一列，因为这些位置只能从前一个位置移动过来。即 dp[i][0] = dp[i-1][0]+coins[i][0] 或 dp[0][j] = dp[0][j-1]+coins[0][j]。
3. 对于dp[i][j]，根据从上方和左方状态转移过来的硬币数量选择收集其中的最小值，因为我们要收集最少的硬币。即 dp[i][j] = min(dp[i-1][j], dp[i][j-1])+coins[i][j]。
4. 最后返回dp[m-1][n-1]，即机器人按照最优路径收集硬币的最少数量。 以下是C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int coinCollect(vector<vector<int>>& coins) {
    int m = coins.size();
    int n = coins[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = coins[0][0];
    // 处理第一行和第一列
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i-1][0]+coins[i][0];
    }
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j-1]+coins[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])+coins[i][j];
        }
    }
    return dp[m-1][n-1];
}
int main() {
    vector<vector<int>> coins = {{1,3,1},
                                 {1,5,1},
                                 {4,2,1}};
    int res = coinCollect(coins);
    cout << "最少需要收集的硬币数量为：" << res << endl; // 最少需要收集的硬币数量为：7
    return 0;
}

可以看到，该算法得到的最少需要收集的硬币数量是7，而不是8。