제목 설명

mxn의 바둑판의 한 칸마다 선물이 하나 놓여 있고 선물마다 일정한 가치가 있다(가치가 0보다 크다)

바둑판의 왼쪽 상단부터 칸에 있는 선물을 들고 매번 오른쪽으로 또는 아래로 한 칸씩 이동해서 바둑판의 오른쪽 하단에 도착할 수 있다

바둑판과 그 위에 있는 선물을 정해 주십시오. 당신이 가장 많은 가치를 얻을 수 있는 선물을 계산해 주십시오

제목 해독

검지 Offer 233

사고방식이 하나, 귀착, 이해하기 쉽지만, 사고방식이 빠르지 않으면, 귀착은 순환보다 시간이 많이 걸릴 것이다

사고방식 2. 책에서 사고방식, 책에서 상세하게 설명하지만 약간 이해하기 어려운 것 같아서 스스로 그림을 그려서 이해를 강화할 것을 건의합니다

코드

사고방식이 첫째, 점차적으로 실현되고 둘째로 실현된다

class Solution {
public:
    int movingCountCore(int *giftMatrix, int rows, int cols, int row, int col){
        int xia = 0, you = 0;
        int result = 0;

        //  
        if(row < rows-1){
            xia = movingCountCore(giftMatrix, rows, cols, row+1, col);
        }

        //  
        if(col < cols-1){
            you = movingCountCore(giftMatrix, rows, cols, row, col+1);
        }
        
        result = xia > you ? xia : you;
        return result + giftMatrix[row * cols + col];
    }

    int movingCount(int *giftMatrix, int rows, int cols){
        if(rows <= 0 || cols <= 0){
            return 0;
        }
        return movingCountCore(giftMatrix, rows, cols, 0, 0);
    }
};

int main(){
    int giftMatrix[] = {1, 10, 3, 8, 12 , 2, 9, 6, 5, 7, 4, 11, 3, 7, 16, 5};
    int rows = 4; 
    int cols = 4;
    Solution ss;
    cout<

사고방식 2, 책에서

#include
using namespace std;

class Solution {
public:

    int max_gift(int *present, int rows, int cols){
        
        if (present == NULL || rows < 1 || cols < 1){
            return 0;
        }

        int* maxValues = new int[cols]; //  0

        for (int i = 0; i < rows; ++i){
            for (int j = 0; j < cols; ++j){
                int up = 0;
                int left = 0;

                if (i > 0){
                    up = maxValues[j];
                }

                if (j > 0){
                    left = maxValues[j-1];
                }

                maxValues[j] = max(up, left) + present[i * cols + j];
            }
        }

        int max_value = maxValues[cols-1];
        delete[] maxValues;

        return max_value;
    }
};

int main()
{
    Solution ss;
    int rows = 4; 
    int cols = 4;
    int present[16] = {1, 10,  3,  8, 
                      12,  2,  9,  6, 
                       5,  7,  4, 11, 
                       3,  7, 16,  5};

    cout<

총결산 전망

사고방식은 더욱 강하고 사고방식은 차례차례 실현되면 더욱 간결해진다

나는 분할선, 나는 분할선, 나는 분할선

1차 귀속 실현, 2차 볼 때 쓰레기 같아. 코드를 잘 못 썼어. 삭제하지 않는 건 자신의 성장을 증명하기 때문이지

#include
using namespace std;

class Solution {
public:

    int max_gift_core(int *present, int rows, int cols, int row, int col){
        int you = 0;
        int xia = 0;
        int result = 0;

        //  
        if (col < cols-1){
            you =  present[row * cols + col+1];   
        }

        //  
        if (row < rows-1){
            xia = present[(row+1) * cols + col];
        }

        if (you > xia){
            result = max_gift_core(present, rows, cols, row, col+1);
        }
        else if(xia > you){
            result = max_gift_core(present, rows, cols, row+1, col);
        }
        else{ // you = xia， 
            if (you != 0){ //  0， ， 
                result = max_gift_core(present, rows, cols, row, col+1);
            }
            else{ //  you=xia=0， 
                result = 0;
            }
        }

        return present[row * cols + col] + result;
    }

    int max_gift(int *present, int rows, int cols){
        
        if (present == NULL || rows < 1 || cols < 1){
            return 0;
        }

        return max_gift_core(present, rows, cols, 0, 0);
    }
};

int main()
{
    Solution ss;
    int rows = 4; 
    int cols = 4;
    int present[16] = {1, 10,  3,  8, 
                      12,  2,  9,  6, 
                       5,  7,  4, 11, 
                       3,  7, 16,  5};

    cout<

귀속 사상을 응용하는 데 있어서 약간의 문제가 있다. 매번 구하는 것이 반드시 전체 국면에서 가장 좋은 것은 아니다. 이 점에 대해 탐구해야 한다. 이 점에 대해 2차 사고는 양자가 같다고 판단할 때 아래로 오른쪽으로 직접 내려가면 된다. 2차 귀속 실현을 직접 보자