1 金矿问题（Gold Mine Problem）

给定一个N*M尺寸的金矿，每个点都有一个非负数表示当前点所含的黄金数目，最开始矿工位于第一列，但是可以位于任意行。矿工只能向右，右上，右下三个方向移动。问该如何安排路线使得所挖的黄金的数量最多？

2 源程序（2种算法）：

using System;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
    public static partial class Algorithm_Gallery
    {
        private static int Collect_Gold(int[,] gold, int r, int c, int n, int m)
        {
            // Base condition.
            if ((r < 0) || (r == n) || (c == m))
            {
                return 0;
            }

            int rightUpperDiagonal = Collect_Gold(gold, r - 1, c + 1, n, m);

            int right = Collect_Gold(gold, r, c + 1, n, m);

            int rightLowerDiagonal = Collect_Gold(gold, r + 1, c + 1, n, m);

            return gold[r, 0] + Math.Max(Math.Max(rightUpperDiagonal, rightLowerDiagonal), right);
        }

        public static int Get_Maxium_Gold(int[,] gold)
        {
            int n = gold.GetLength(0);
            int m = gold.GetLength(1);
            int maxGold = 0;
            for (int i = 0; i < n; i++)
            {
                int goldCollected = Collect_Gold(gold, i, 0, n, m);
                maxGold = Math.Max(maxGold, goldCollected);
            }

            return maxGold;
        }

        private static int Collect_Gold(int[,] gold, int r, int c, int n, int m, int[,] dp)
        {
            if ((r < 0) || (r == n) || (c == m))
            {
                return 0;
            }

            if (dp[r, 0] != -1)
            {
                return dp[r, 0];
            }

            int rightUpperDiagonal = Collect_Gold(gold, r - 1, c + 1, n, m, dp);

            int right = Collect_Gold(gold, r, c + 1, n, m, dp);

            int rightLowerDiagonal = Collect_Gold(gold, r + 1, c + 1, n, m, dp);

            return gold[r, 0] + Math.Max(Math.Max(rightUpperDiagonal, rightLowerDiagonal), right);
        }

        public static int Get_Maxium_Gold_Second(int[,] gold)
        {
            int n = gold.GetLength(0);
            int m = gold.GetLength(1);
            int maxGold = 0;
            int[,] dp = new int[n, m];
            for (int row = 0; row < n; row++)
            {
                for (int col = 0; col < m; col++)
                {
                    dp[row, col] = -1;
                }
            }
            for (int i = 0; i < n; i++)
            {
                int goldCollected = Collect_Gold(gold, i, 0, n, m, dp);
                maxGold = Math.Max(maxGold, goldCollected);
            }

            return maxGold;
        }
    }
}
 

3 源程序

using System;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class Algorithm_Gallery{private static int Collect_Gold(int[,] gold, int r, int c, int n, int m){// Base condition.if ((r < 0) || (r == n) || (c == m)){return 0;}int rightUpperDiagonal = Collect_Gold(gold, r - 1, c + 1, n, m);int right = Collect_Gold(gold, r, c + 1, n, m);int rightLowerDiagonal = Collect_Gold(gold, r + 1, c + 1, n, m);return gold[r, 0] + Math.Max(Math.Max(rightUpperDiagonal, rightLowerDiagonal), right);}public static int Get_Maxium_Gold(int[,] gold){int n = gold.GetLength(0);int m = gold.GetLength(1);int maxGold = 0;for (int i = 0; i < n; i++){int goldCollected = Collect_Gold(gold, i, 0, n, m);maxGold = Math.Max(maxGold, goldCollected);}return maxGold;}private static int Collect_Gold(int[,] gold, int r, int c, int n, int m, int[,] dp){if ((r < 0) || (r == n) || (c == m)){return 0;}if (dp[r, 0] != -1){return dp[r, 0];}int rightUpperDiagonal = Collect_Gold(gold, r - 1, c + 1, n, m, dp);int right = Collect_Gold(gold, r, c + 1, n, m, dp);int rightLowerDiagonal = Collect_Gold(gold, r + 1, c + 1, n, m, dp);return gold[r, 0] + Math.Max(Math.Max(rightUpperDiagonal, rightLowerDiagonal), right);}public static int Get_Maxium_Gold_Second(int[,] gold){int n = gold.GetLength(0);int m = gold.GetLength(1);int maxGold = 0;int[,] dp = new int[n, m];for (int row = 0; row < n; row++){for (int col = 0; col < m; col++){dp[row, col] = -1;}}for (int i = 0; i < n; i++){int goldCollected = Collect_Gold(gold, i, 0, n, m, dp);maxGold = Math.Max(maxGold, goldCollected);}return maxGold;}}
}