堆砖块

@JacobGo！@minnnng@chorus 这三位的状态转移表述都是错的，虽然本题中不影响结果，但是不利于理解。

以下是正确表述

dp[j]表示B-A+sum为j时，B堆的最大高度

所以把砖块放在B堆时:dp1[j]=dp0[j-h]+h

A堆:dp1[j]=dp0[j+h]

不放：dp1[j]=dp0[j]

这才是正确状态转移，三位互相借鉴的时候就不能仔细看一遍？？

自己的代码分明是将A-B+sum作为j，为何注释里要说成B-A+sum，误人子弟。

以下是我的代码

import java.util.Arrays; 
import java.util.Scanner; 
public class Main{ public static void main(String[] args) {
    Scanner scan=new Scanner(System.in); 
    int n=scan.nextInt(); 
    int[] heights=new int[n]; 
    int count=0; 
    for(int i=0;i;i++){
        heights[i]=scan.nextInt(); 
        count+=heights[i]; 
    } 
    int[] dp1=new int[2*count+1]; 
    int[] dp0=new int[2*count+1]; 
    for(int i=0;i2*count+1;i++){
        dp0[i]=-1; 
    }
    dp0[count]=0; 
    for(int i=1;i1;i++){ 
         int height=heights[i-1]; 
         for(int j=0;j2*count+1;j++){
             dp1[j]=dp0[j]; 
             if(j-height>=0&&dp0[j-height]!=-1){
                 dp1[j]=Math.max(dp1[j],dp0[j-height]+height); 
             }             
             if(j+height2*count&&dp0[j+height]!=-1){
                 dp1[j]=Math.max(dp1[j],dp0[j+height]); 
             }
         } 
         for(int j=0;j2*count+1;j++){
             dp0[j]=dp1[j]; 
         }
     } 
     int max=-1; 
     for(int i=1;i1;i++){
        max=Math.max(max,dp0[count]); 
     }
     System.out.println(max==0?-1:max); 
     }
}

/*
                 动态规划解决。(用砖堆两个塔，A塔和B塔,B塔-A塔高度差为: -sumHeight~sumHeight，防止数组下表越界，加上sumHeight)。

	 dp[i][j]表示使用前 i 块砖，B-A 塔高度差为 j 时 B 塔的最大高度。  则解为  dp[n][0].使用滚动数组方法解决当 n 过大时 dp[n+1][2*sumHeight+1]二维数组占用内存过高问题,状态转移方程为:

	  					dp[i-1][j], 第 i 块砖不用

	 dp[i][j] =  max    dp[i-1][j-height[i]], 第 i 块砖放在 A 塔

	   					dp[i-1][j+height[i]] + height[i], 第 i 块砖放在 B 塔


	


	*/
import java.util.*;
public class PileOfBricks {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			int n = scan.nextInt();
			int[] height = new int[n+1];
			int sumHeight = 0;
			for(int i=1; i<=n ;i++){
				height[i] = scan.nextInt();
				sumHeight += height[i];
			}
			
			int[][] dp = new int[2][2*sumHeight+1];
			
			for(int i=0; i<2*sumHeight+1; i++)
				dp[0][i] = -1;
			
			dp[0][sumHeight] = 0;
			
			for(int i=1; i<=n; i++){
				for(int j=0; j<2*sumHeight+1; j++){
					dp[1][j] = dp[0][j];
					if(j-height[i]>=0 && dp[0][j-height[i]]!=-1)
						dp[1][j] = Math.max(dp[1][j], dp[0][j-height[i]]);
					if(j+height[i]<=2*sumHeight && dp[0][j+height[i]]!=-1)
						dp[1][j] = Math.max(dp[1][j], dp[0][j+height[i]]+height[i]);
				}
				int[] temp = dp[0];
				dp[0] = dp[1];
				dp[1] = temp;
			}
			if(dp[0][sumHeight] == 0)
				System.out.println(-1);
			else
				System.out.println(dp[0][sumHeight]);
		}
	}

}