小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。
给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。
C++
class Bonus {
public:
int getMost(vector<vector<int> > board) {
// write code here
// 此处的求出二元组的长宽，其实题目是特殊情况，已经给出
int row = board.size()-1;
if(row == -1)
return 0;
int col = board[0].size()-1;
int **value = new int*[row+1];
for(int i=0; i <= row; i++)
value[i] = new int[col];
value[row][col] = board[row][col];//右下角的一格的价值
/*
最后一列，和最后一行都处于一个特殊情况：
他们只有一个选择到下一格
*/
for(int i=row-1; i>=0; i--)
value[i][col] = board[i][col]+value[i+1][col];
for(int i=col-1; i>=0; i--)
value[row][i] = board[row][i]+value[row][i+1];
/*到达下一格哪一个最优，反推回到第一个(左上角)*/
for(int i=row-1; i>=0; i--)
for(int j=col-1; j>=0; j--)
{
if(value[i+1][j] > value[i][j+1])
value[i][j] = board[i][j] + value[i+1][j];
else
value[i][j] = board[i][j] + value[i][j+1];
}
return value[0][0];
}
};
/*
解题思路：
泥煤的动态规划!!!
解决动态规划的主要方法还是反推回去(建表)，
得到最后一格走法的最优解，得到倒数第二格走法的最优解，得到...
把所有格子的最优解由下到上求解出来，即可得到(0,0)的最优解
*/
参考链接：矩阵上寻找最短路径