问题描述

在二维动态规划中，一道经典的问题就是移动机器人的移动问题，这个问题的描述是这样的：

有一个移动机器人，可以在二维矩阵平面中移动，其移动的起点位于左上角，每次移动只能向右或者向下，其移动的终点是右下角，在这个矩阵形的平面中每个位置都有一个数值，代表机器人在经过这个区域时需要付出的代价。我们的目标就是，在这个平面中，找一条代价最小的路径，并且输出最小代价路径和以及打印最小代价路径。

那么这个问题我们首先可以确定的是，它是一道动态规划问题。然后这个问题需要分两步进行解答，分别是第一步通过通过动态规划得到最小代价和，然后打印最短路径。

最小代价路径和

这事一个很明显的动态规划问题，我们以一个例子进行分析。如我们给出的数据是这样的。

那我们首先定义数组

 vector<vector<int>>data{{2,3,1},{1,9,1},{6,4,2}};

然后需要定义动态规划数组dp

vector<vector<int>>dp{{0,0,0},{0,0,0},{0,0,0}};

接下来确定我们的动态规划思路：

1、既然只能向右向下运动，那么就可以按照一定次序进行遍历每个位置，例如按照行遍历。

2、机器人在每个位置处动态规划数组的值应该是当前的代价，加上其上面和左边代价中最小的值（为了保证最小代价）

3、当遇到边界条件时，只能取上面或者左面中的一个，也就没必要比较大小了。

4、第一个元素也就是左上角的地方的值涉及两个方向都越界也需要单独处理。

代码如下：

    for(int i =0;i<data.size();i++){
        for(int j = 0;j<data[0].size();j++){
            if ((i-1)>=0&&(j-1)>=0){
                dp[i][j] = data[i][j]+min(dp[i-1][j],dp[i][j-1]);
            }
            else if((i-1)<0&&(j-1)<0){
                dp[i][j] = data[i][j];
            }
            else{
                if((i-1)<0){
                    dp[i][j] = data[i][j]+dp[i][j-1];
                }
                else{
                    dp[i][j] = data[i][j]+dp[i-1][j];
                }
            }
        }
    }
    cout<<"min_sum="<<dp[data.size()-1][data[0].size()-1]<<endl;

这样我们就可以得到最小的路径和了

打印最小代价路径

打印最短路径时，我们必须从后向前找，因为当我们通过前向得到每个位置的dp值时，并不能保证当时的值就是最终的最小值，这也正式动态规划的魅力所在。因此我们只能从后向前遍历。

而因为我们得到的最小代价路径是最小的，因此也就是说，当最后一个位置的dp值减去此处的代价后，得到的dp值一定就是我们需要找的值，而这个值只能存在于当前位置的上面或者左边。

因此顺着这个思路，我们就可以写如下代码：

    int n = data.size()-1;
    int m = data[0].size()-1;
    int tmp = dp[data.size()-1][data[0].size()-1];
    int i = n;
    int j = m;
    while(i>=0&&j>=0){
        cout<<data[i][j]<<endl;
        if(i==0||j==0){
            if(i==0)
                j =j-1;
            else{
                i = i-1;
            }
        }
        else{
        if (dp[i-1][j]==dp[i][j]-data[i][j]){
            i = i-1;
        }
        else{
            j = j-1;
        }
    }}

这其中i一个if是为了保证边界条件，而else则是根据匹配的dp值，更新前一步的位置。

最终打印的路径如下：

对应的就是这条路径

may the force be with you！