47:선물의 최대치(동적 기획)

제목: m*n의 바둑판에는 칸마다 선물을 하나씩 넣고 선물마다 가치가 있다.(0,0)부터 출발해서 오른쪽, 또는 아래로 내려가서 오른쪽 아래로 내려가서 선물의 최대 가치를 구할 수 있다
생각:![여기에 그림 설명 삽입]https://img-blog.csdnimg.cn/20190420132748945.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5saWppbmdyYW4=,size_16,color_FFFFFF,t_70

public int func(int[][] gifts) {
        if(gifts==null||gifts.length==0)
            return 0;
        //maxGift[i,j]   (i,j)         
        int[][] maxGift=new int[gifts.length][gifts[0].length];
        maxGift[0][0]=gifts[0][0];

        for(int i=0;i0){
                    upMax=maxGift[i-1][j];
                }
                if(j>0){
                    leftMax=maxGift[i][j-1];
                }
                maxGift[i][j]=Math.max(leftMax,upMax)+gifts[i][j];
            }
        }
        return maxGift[gifts.length-1][gifts[0].length-1];
    }

공간 복잡성 최적화:
1차원 그룹으로만 이전 줄의 최대 선물 값을 저장하는 것이지 전체 2차원 그룹의 칸마다 최대 선물 값을 저장하는 것이 아니다

    public int func2(int[][] gifts) {
        if(gifts==null||gifts.length==0)
            return 0;
        //maxGift[j]   (i-1,j)         
        int[] maxGift=new int[gifts[0].length];
        for(int i=0;i0){
                    upMax=maxGift[j];
                }
                if(j>0){
                    leftMax=maxGift[j-1];
                }
                maxGift[j]=Math.max(leftMax,upMax)+gifts[i][j];
            }
        }
        return maxGift[gifts[0].length-1];
    }