题解 | #拜访#

什么是动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

如何使用动态规划的思想解决此题

1.定义一个二维的dp数组，其中的元素与地图上的一 一对应，表示从我的地方（xMe,yMe）到该位置(i,j)的有几条最短路径

dp[i][j] ：表示从（xMe,yMe）出发，到(i, j) 有dp[i][j]条不同的路径，程序最后返回dp[xDes][yDes]即可（（xDes，yDes）是专家的位置）。

2.dp[i][j]的值如何得到呢？

由dp[i][j]的上一个可能的状态（有 dp[i - xDir][j] 和dp[i][j - yDir]）得到。这里的xDir和yDir表示运动方向，见程序31、32行。

即dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

但这里需要注意一点，因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。

3.确定了dp的获得方式和之前的状态有关之后，我们需要给dp一个初始的值，这样才能得到后面的值

初始的值选用边界是最好计算的，因为在最短路径中，能到达边界的方法只有一种。但是考虑到边界中可能出现障碍物，所以在边界中障碍物对应的dp值置零，其余置一。

4.确定遍历顺序，本题中从x开始遍历和从y开始遍历都可以，我选择从x开始遍历。

5.输出结果dp[xDes][yDes]

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param CityMap int整型二维数组 
 * @param CityMapRowLen int CityMap数组行数
 * @param CityMapColLen int* CityMap数组列数
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */

int countPath(int** CityMap, int CityMapRowLen, int* CityMapColLen, int n, int m ) {
    // write code here
    int i,j;//定义工具人
    int xDes,yDes,xMe,yMe;//定义客户的位置（xDes、有yDes）和我的位置（xMe、yMe）
    int **dp = malloc(sizeof(int *) * n);
    for(i = 0; i < n; i++){
        dp[i] = malloc(sizeof(int) * m);
        for(j = 0; j < m; j++){
            if(CityMap[i][j] == 1){
                xMe = i;
                yMe = j;
            }
            if(CityMap[i][j] == 2){
                xDes = i;
                yDes = j;
            }
        }
    }
    int xDir = xMe > xDes ? -1 : 1;     //定义x方向
    int yDir = yMe > yDes ? -1 : 1;     //定义y方向
    dp[xMe][yMe] = 1;
    for(i = xMe + xDir; i != xDes + xDir; i += xDir){
        if(CityMap[i][yMe] == -1){
            dp[i][yMe] = 0;
        }else{
            dp[i][yMe] = 1;
        }      
    }
    for(i = yMe + yDir; i != yDes + yDir; i += yDir){
        if(CityMap[xMe][i] == -1){
            dp[xMe][i] = 0;
        }else{

            dp[xMe][i] = 1;
        }     
    }
    for(i = xMe + xDir; i != xDes + xDir; i += xDir){
        for(j = yMe + yDir; j != yDes + yDir; j += yDir){
            if(CityMap[i][j] == -1){
                dp[i][j] = 0;
            }
            dp[i][j] = dp[i - xDir][j] + dp[i][j - yDir];   
        }
    }
    return dp[xDes][yDes];
}