leetcode 刷题

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

• 只能从架子的左上角开始拿珠宝
• 每次可以移动到右侧或下侧的相邻位置
• 到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

示例 1：

输入：frame = [[1,3,1],[1,5,1],[4,2,1]]
输出：12
解释：路径 1→3→5→2→1 可以拿到最高价值的珠宝

动态规划：

int dfs(int ** memo,int** frame,int n,int m){
    if(n < 0 || m < 0){
        return 0;
    }
    if(memo[n][m] != -1){
        return memo[n][m];
    }else{
        memo[n][m] = fmax(dfs(memo,frame,n-1,m),dfs(memo,frame,n,m-1)) + frame[n][m];
        return memo[n][m];
    }
}
int jewelleryValue(int** frame, int frameSize, int* frameColSize) {
    int N = frameSize,M = frameColSize[0];
    int** memo = (int**)malloc(N*sizeof(int*));
    for(int i = 0;i < N;i++){
        memo[i] = (int*)malloc(M*sizeof(int));
        for(int j = 0;j < M;j++){
            memo[i][j] = -1;
        }
    }
    int result = dfs(memo,frame,N-1,M-1);
    for(int i = 0;i < N;i++){
        free(memo[i]);
    }
    free(memo);
    return result;
}

如果有负数，下面这段代码就不适用了

    if(n < 0 || m < 0){
        return 0;
    }

因为假如一路选过来都是负数，fmax()中一个是越界访问值0，另一个是负数，那么较大值是0，就出错了，应更改为：

if(n < 0 || m < 0){
    return -INT_MAX;
}

当有负数时还有一种情况就是行列下标都为零时，此时dfs[0][0] = fmax(dfs[-1][0],dfs[0][-1]) + frame[0][0] ,一定是负无穷，又不对了。所以对这个点要单独讨论。

if( ==0 && m==0){
    return frame[0][0];
}