4/18剑指offer

1.礼物的最大价值
思路一：利用动态规划的思想，先用递归的思路分析。先定义第一个函数f（i，j）表达能到达坐标f（i，j）的格子时能拿到礼物总和的最大值。根据题目要求，有两种可能的途径到达坐标为（i，j）的格子。因此的状态转移方程为f(i,j)=max(f(i-1,j),f(i,j-1))+gift[i,j]。

    int getMaxValue_solution1(const int*values,int rows,int cols)
    {
        if(values==nullptr||rows<=0||cols<=0)
        {
            return 0;//特殊情况
        }
        int **maxValues=new int*[rows];
        for(int i=0;i<rows;i++)
        {
            maxValues[i]=new int[cols];
        }
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                int left=0;
                int up=0;
                if(i>0)
                up=maxValues[i-1][j];
                if(j>0)
                left=maxValues[i][j-1];//特殊条件
                maxValues[i][j]=max(left,up)+values[i*cols+j];//状态转移方程
            }
        }
        int maxValue=maxValues[rows-1][cols-1];//最后的值就是矩阵右下角的值
        for(int i=0;i<rows;++i)
        {
            delete[] maxValues[i];
        }
        delete maxValues;
        return maxValue;
    }

思路二：考虑进一步的优化，因为到达坐标为（i，j）的格子时能够拿到的礼物的最大价值只与两个格子有关，即(i-1,j)与（i,j-1），因此第i-2行及更上面的所有格子礼物的最大价值实际没必要保存。可以利用一个一维数组来代替上述的二维矩阵。改一维数组的长度为棋盘的列数n。当计算到(i,j)的格子时能够拿到最大价值为f(i,j),数组前j个数字分别是f(i,0)到f(i,j-1),数组从下标为j的数字开始到最后一个数字，分别为f(i-1,j)到f(i-1,n-1),也就是说，该数组前面j个数字分别是当前第i行前面j个格子礼物的最大价值，而之后的数字分别保存前面第i-1行n-j个格子礼物的最大价值。

    int getMaxValue_solution1(const int*values,int rows,int cols)
    {
        if(values==nullptr||rows<=0||cols<=0)
        {
            return 0;//特殊情况
        }
        int *maxValues=new int[cols];
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                int left=0;
                int up=0;
                if(i>0)
                up=maxValues[j];
                if(j>0)
                left=maxValues[j-1];
                maxValues[i][j]=max(left,up)+values[i*cols+j];//状态转移方程
            }
        }
        int maxValue=maxValues[cols-1];//最后的值就是最右面的值
        delete maxValues;
        return maxValue;
    }
};