小東所在公司要發年終獎，而小東恰好獲得了最高福利，他要在公司年會上參與一個抽獎游戲，游戲在一個6 * 6的棋盤上進行，上面放著36個價值不等的禮物，每個小的棋盤上面放置著一個禮物，他需要從左上角開始游戲，每次只能向下或者向右移動一步，到達右下角停止，一路上的格子里的禮物小東都能拿到，請設計一個算法使小東拿到價值最高的禮物。

　　給定一個6 * 6的矩陣board，其中每個元素為對應格子的禮物價值,左上角為[0, 0], 請返回能獲得的最大價值，保證每個禮物價值大于100小于1000。

　　京東2015年校園招聘題目，是一道動態規劃問題，首先寫出其遞推表達式：dp[i][j]=board[i][j]+max(dp[i-1][j],dp[i][j-1])(x>=1&&y>=1)

　　然后就很容易寫出代碼了：

class Bonus { public:int getMost(vector<vector<int> > board) {for (int i = 1; i < 6; i++) {board[i][0] += board[i - 1][0];board[0][i] += board[0][i-1];}for (int i = 1; i < 6; i++) {for (int j = 1; j < 6; j++) {board[i][j] = max(board[i - 1][j], board[i][j - 1])+board[i][j];}}return board[5][5];} };

　　

?

轉載于:https://www.cnblogs.com/shenshenlei/p/5535116.html

總結

以上是生活随笔為你收集整理的基本动态规划问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。