棋盘寻宝
題目描述：
輸入：
輸出：
現在有一個8*8的棋盤，上面放著64個價值不等的禮物，每個小的棋盤上面放置一個禮物（禮物的價值大于0小于1000），一個人的初始位置在棋盤的左上角，每次他只能向下或向右移動一步，并拿走對應棋盤上的禮物，結束位置在棋盤的右下角，請設計一個算法使其能夠獲得最大價值的禮物。
輸入包含多個測試用例，每個測試用例共有8行8列，第i行的第j列的數字代表了該處棋盤上的禮物的價值，每兩個數之間用空格隔開。
對于每組測試用例，請輸出你能夠獲得最大價值的禮物。
樣例輸入：
2 8 15 1 10 5 19 19 3 5 6 6 2 8 2 12 16 3 8 17 12 5 3 14 13 3 2 17 19 16 8 7 12 19 10 13 8 20 16 15 4 12 3 14 14 5 2 12 14 9 8 5 3 18 18 20 4 2 10 19 17 16 11 3 動態規劃問題：
dp[i][j]=dp[i][j-1]+dp[i-1][j]
?dp[0][0]=map[0][0];
? ? ? ? 把列為0行為1到7的所有的最優的dp[i][0]求出；dp[i][0]=dp[i-1][0]+map[i][j];
? ? ? ? 把行為0列為1到7的所有的最優的dp[0][j]求出; ? dp[0][j]=dp[0][j-1]+map[i][j];
? ? ? ? 然后再由
? ? ? ? ?for(i=1;i<8;i++)
? ? ? ? ? ? ? for(j=1;j<8;j++)
? ? ? ? ? ? ? ? ? ? ? dp[i][j]=max{dp[i-1][j],dp[i][j-1]};
? ? ? ?其中dp[i-1][j]表示左邊走過來的，dp[i][j-1]表示上邊走下來的
dp[0][0]=map[0][0];把列為0行為1到7的所有的最優的dp[i][0]求出；dp[i][0]=dp[i-1][0]+map[i][j];把行為0列為1到7的所有的最優的dp[0][j]求出; dp[0][j]=dp[0][j-1]+map[i][j];然后再由for(i=1;i<8;i++)for(j=1;j<8;j++)dp[i][j]=max{dp[i-1][j],dp[i][j-1]};其中dp[i-1][j]表示左邊走過來的，dp[i][j-1]表示上邊走下來的總結
- 上一篇： 斐波那契查找
- 下一篇： Maximum Product Suba