动态规划--左上角到右下角的最大收益问题

[size=medium]无权重：
问题描述：请编写一个函数（允许增加子函数），计算n x m的棋盘格子（n为横向的格子数，m为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。[/size]
[table]
|| || ||
|| || ||
|| || ||
|| || ||
[/table]
[size=medium]这时ｎ×ｍ的棋盘格子边缘线共有（ｎ＋１）＊（ｍ＋１）条，状态转移方程式
　

dp[i][j] = dp[i][j-1]+dp[i-1][j];
//初始化的话：
dp[i][0]=0;dp[0][j]=0;

因此核心代码如下：[/size]

int[][] dp = new int[n+1][m+1];
		//注意，以下的dp走的不是格子，而是外围的线
		for(int i=1;i<=n;i++){
			dp[i][0]=1;
		}
		for(int i=1;i<=m;i++){
			dp[0][i]=1;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				dp[i][j]=dp[i-1][j]+dp[i][j-1];
			}
		}

		return dp[n][m];

含有权重:
[size=medium]平面上有N*M个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始，每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来，这样下去，你最多能收集到多少个苹果。
每个格子dp[i][j]能取的最多苹果是max(dp[i-1][j],dp[i][j])+A[i][j]（表示（i，j）这个格子所含有的最多的苹果））
对第一行，第一列进行初始化[/size]

//下面这些代码初始化是错误的，因为我们不是将A[i][j]放进去，而是对其进行加减
for(int i=0;i<n;i++){
    dp[0][i] = A[0][i];
}
for(int i=0;i<n;i++){
    dp[i][0] = A[i][0];
}
//而后就是状态转移方程的核心代码
                    for(int i=0;i<n;i++){
		    for(int j=0;j<m;j++){
		    	int increment = A[i][j];
		    	int left = 0;
		    	int up = 0;
		    	if(i>0){
		    		up=dp[i-1][j];
		    	}
		    	if(j>0){
		    		left=dp[i][j-1];
		    	}
		    	int neighbor = up>left?up:left;
		    	dp[i][j] = neighbor+increment;
		    	System.out.print(dp[i][j]+"\t");

		    	//当i=0，或者j=0时，neighbor=0;A[0][0],初始化完成，而后i=0;j=1时，left=A[0][0],dp[0][1]初始化完成
		    	//同理，对于第一列也是如此
		  }
		    System.out.println();
		}
		System.out.println(dp[n-1][m-1]);
	}