题目描述
在一个m*n的棋盘每个格有一个礼物，每个礼物有一定价值（>0）。从棋盘左上角到右下角，只能向下或向右走，问能拿到的礼物最大价值。
解题思路
dp。
可将二维数组版优化为一维数组版。
代码
一维数组版
#include <iostream>
using namespace std;
int maxSum(int* val,int rows,int cols){
if(!val||rows<=0||cols<=0){
return -1;
}
int dp[cols];
memset(dp, 0, sizeof(dp));
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(i==0&&j==0){
dp[j]=val[i*cols+j];
}
else if(i==0){
dp[j]=dp[j-1]+val[i*cols+j];
}
else if(j==0){
dp[j]=dp[j]+val[i*cols+j];
}
else{
dp[j]=max(dp[j],dp[j-1])+val[i*cols+j];
}
}
}
return dp[cols-1];
}
int main(int argc, const char * argv[]) {
int val[]={1,2,3,4,5,6};
int rows=2;
int cols=3;
int* pVal=val;
int sum=maxSum(pVal, rows, cols);
cout<<sum<<endl;
return 0;
}
二维数组版
#include <iostream>
using namespace std;
int maxSum(int* val,int rows,int cols){
if(!val||rows<=0||cols<=0){
return -1;
}
int dp[rows][cols];
memset(dp, 0, sizeof(dp));
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(i==0&&j==0){
dp[i][j]=val[i*cols+j];
}
else if(i==0){
dp[i][j]=dp[i][j-1]+val[i*cols+j];
}
else if(j==0){
dp[i][j]=dp[i-1][j]+val[i*cols+j];
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+val[i*cols+j];
}
}
}
return dp[rows-1][cols-1];
}
int main(int argc, const char * argv[]) {
int val[]={1,2,3,4,5,6};
int rows=2;
int cols=3;
int* pVal=val;
int sum=maxSum(pVal, rows, cols);
cout<<sum<<endl;
return 0;
}