Question

考点

算法-动态规划算法-动态规划算法

面5笔5

8*8的棋盘的每个小格里放着一个价值互不相同的礼物，一个人初始位置在左上角，每次只能向下或者向右走一步，并获得相应位置的礼物，结束位置在棋盘的右下角，设计一个算法能够使得到的礼物的总价值最大

Answer 1

解答

思路：

考虑中间状态

·设D[i][j]为棋盘位置(i,j)时，可以获得的最大价值; val[i][j]为（i, j）位置礼物的价值

·则有D[i][j] = max(D[i][j-1], D[i-1][j]) +val[i][j]

·边界值是D[0][0] = val[0][0],

·因为算法中用到i-1和j-1的值，为书写方便，先处理边界处的值

代码：

int getMaxPrice(int [][]D, int [][]val, int n)
{
    int i = 0 ;
    int j = 0;

    D[0][0] = val[0][0];
     //处理边界
    for(i = 1; i< n ; i ++)
         D[i][0] = D[i-1][0]  +val[i][0];
    for(j = 1; j< n; j++)
         D[0][j] = D[0][j-1] +val[0][j];
    for(i = 1; i< n; i++)
    {
           for( j= 1; j < n; j ++)
                  D[i][j] = max(D[i][j-1], D[i-1][j]) +val[i][j];
    }    
    return D[n-1][n-1];
}