方法一：顺推法
根据题意，可以得出转移方程式：
dp[i][j]=max(dp[i−1][j−1],dp[i−1][j])+a[i][j]dp[i][j]=\max(dp[i-1][j-1],dp[i-1][j])+a[i][j] dp[i][j]=max(dp[i−1][j−1],dp[i−1][j])+a[i][j]
如果把a[i][j]a[i][j]a[i][j]忽略，改成变量kkk，也不会有什么大碍。因此，可以写出下列代码：
方法二：一维顺推
这道题目出题人很善良，所谓的行数rrr满足要求：
1≤r≤1001\leq r\leq100 1≤r≤100
当然，如果所谓的行数rrr过大超过大约300030003000的话，由于状态转移方程式中只涉及到dp[i−1][j]dp[i-1][j]dp[i−1][j]和dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1]两者，可以考虑只开一维数组（当然也可以开滚动数组），代替二维。
状态转移方程式变为了：
dp[j]=max(dp[j−1],dp[j])+kdp[j]=\max(dp[j-1],dp[j])+k dp[j]=max(dp[j−1],dp[j])+k
唯一的麻烦就是如果从左往右存储会发生当m=j+1m=j+1m=j+1时，dp[j]dp[j]dp[j]发生改变后dp[m]=max(dp[m−1],dp[m])+kdp[m]=max(dp[m-1],dp[m])+kdp[m]=max(dp[m−1],dp[m])+k这里dp[m−1]dp[m-1]dp[m−1]已经是更新过后的值了，不符合题意。因此，必须从右往左存储。
方法三：逆推法
顺推法有优点也有缺点。优点是方法简单容易想到，而且可以优化空间省去数组a[101][101]a[101][101]a[101][101]。
但是缺点是它有多个终点，直接输出dp[n][n]dp[n][n]dp[n][n]明显不是最大值，必须遍历一遍获得最大值输出。
因此，我们可以考虑设置多个起点出发回到同一个终点。这就是逆推法主要思想。
状态转移方程式：
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]dp[i][j]=\max(dp[i+1][j],dp[i+1][j+1])+a[i][j] dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]
当然，这里需要先输入所有的a[i][j]a[i][j]a[i][j]，再进行逆推过程，不能省去a[101][101]a[101][101]a[101][101]这个二维数组。
方法四：一维逆推
和顺推法一样，逆推法的dp[101][101]dp[101][101]dp[101][101]是二维数组，当所谓的行数rrr超过大约300030003000时，空间就会不够。因此，我们考虑逆推法的一维状态转移方程式。
由逆推法知道，dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]dp[i][j]=\max(dp[i+1][j],dp[i+1][j+1])+a[i][j]dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]，dp[i][j]dp[i][j]dp[i][j]只取决于dp[i+1][j]dp[i+1][j]dp[i+1][j]和dp[i+1][j+1]dp[i+1][j+1]dp[i+1][j+1]，因此降维操作不影响结果，则状态转移方程式变为：
dp[j]=max(dp[j],dp[j+1])+a[i][j]dp[j]=\max(dp[j],dp[j+1])+a[i][j] dp[j]=max(dp[j],dp[j+1])+a[i][j]
令m=j+1m=j+1m=j+1，则先推完dp[j]dp[j]dp[j]，取决于dp[j]dp[j]dp[j]和dp[m]dp[m]dp[m]，而dp[m]dp[m]dp[m]这一轮还没有推；再推dp[m]dp[m]dp[m]，涉及到dp[m]dp[m]dp[m]和dp[m+1]dp[m+1]dp[m+1]，没涉及到dp[j]dp[j]dp[j]。因此，逆推法用一维数组实现，循环不用从后往前，直接从前往后推即可。
