动态规划js

求最大的输出和。从上到下累加和，只能往下或者下右( 比如： 7->3->8->7->5 这个就是最大值30)
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

<script> 
//初始化二维数组，简单一点。
var arr = [];
arr[0] =[];
arr[0][0] = 7;
arr[1] =[];
arr[1][0] = 3;arr[1][1] = 8; 
arr[2] =[];
arr[2][0] = 8;arr[2][1] = 1; arr[2][2] = 0;
arr[3] =[];
arr[3][0] = 2; arr[3][1] = 7; arr[3][2] = 4; arr[3][3] = 4;   
arr[4] =[];
arr[4][0] = 4; arr[4][1] = 5; arr[4][2] = 2; arr[4][3] = 6;  arr[4][4] = 5;
var n = 5;
var maxSum = arr[n-1];
//1. 减2是因为要从倒数第二行开始
for(var i = n-2; i >= 0; i--){
  for(var j = 0; j <= i; j++){
    maxSum[j] = Math.max(maxSum[j], maxSum[j+1]) + arr[i][j]
  }
}
alert(maxSum[0])
// 2. 递归实现的
//   var n = 5;
// function maxsum(i,j){
 
//    if(i == n-1){
//      return arr[i][j];
//    }
//    var x = maxsum(i+1,j);
//    var y = maxsum(i+1,j+1);
 
//    console.log(x,y,arr[i][j]);
//    return Math.max(x, y) + arr[i][j];
// }
// var aa = maxsum(0,0)
// alert(aa)
</script>

第一种递推的算法，就是倒着两个依次累加更换掉倒数第二层，同理依次类推到arr[0][0] 就是累加出来的最大值。但是原来的arr数组已经改变了。
参考： https://blog.csdn.net/ailaojie/article/details/83014821