黑马程序员技术交流社区

标题: 求一个算法。 [打印本页]

---

作者: 张文    时间: 2012-8-20 16:33
标题: 求一个算法。
今天有一个演讲是关于智能游戏开发的，完了有道题大家谁有这个算法。
下列3角形中，获取最大值的串（就是吧3角行的相邻2个点（上下行）串起来，看哪一串最大）
     5
   8 4
  3 6 9
7 2 9 5
结果为 5 + 8 + 6 + 9

求这个3角行有n行时的算法。

---

作者: 许庭洲    时间: 2012-8-20 17:12


从三角形的顶部到底部有很多条不同的路径，对于每条路径，把路径上面的数加起来可以得到一个和，通过动态规划方法找到最大的和。
  int[][] myArray = myMethod.GetMyArray();
  int[] lastArray = null;
  for (int i = myArray.Length; i > 0; i--)
  {
       int[] arr = myArray[i - 1];
       if (lastArray == null)
       {
             lastArray = arr;
       }
       else
      {
            int[] myArr = new int[arr.Length];
            for (int j = 0; j < arr.Length; j++)
            {
                     myArr[j] = arr[j] + Math.Max(lastArray[j], lastArray[j + 1]);
            }
            lastArray = myArr;
       }
  }
  Console.WriteLine("the result = {0}", lastArray[0]);

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2