动态规划之收集苹果

浏览数：31 / 时间：2015年06月11日

路径经过的最大值（最小值）：
原题：平面上有N*M个格子，每个格子中放着一定数量的苹果。从左上角的格子开始，每一步只能向下走或是向右走，每次走到一个格子就把格子里的苹果收集起来，这样一直走到右下角，问最多能收集到多少个苹果。

不妨用一个表格来表示：

    {5, 8, 5, 7, 1, 8},
    {1, 3, 2, 8, 7, 9},
    {7, 8, 6, 6, 8, 7},
    {9, 9, 8, 1, 6, 3},
    {2, 4,10, 2, 6, 2},
    {5, 5, 2, 1, 8, 8},

在这个6X6的表格里面填写了一些数表示所在格子中的苹果数量。根据题目的规则"每一步只能向下走或是向右走"，如果用x表示纵向，用y表示横向，那么能够到达a[x，y]处的只有两个位置a[x-1，y](上一格)和a[x，y-1]（左边一格），所以必然是取这两个位置中比较大的那一个点。依此回溯到a[0，0]，或者从a[0，0]递推到a[x，y]。

......... , ......... , a[x-1，y]

......... , a[x，y-1], a[x，y] ,

基于这一点，我们可以从左上角开始将到达第一行和第一列中各点所能收集到的最大苹果数量填成一张表格。如下：

技术分享

接下来填第2行，首先是第2行第2列的值，应该填写为 MAX（A[1，2], A[2，1]）+ A[2，2]对应的苹果数量。也就是说到达第2行第2列能获得的最大苹果数，要看第2行第1列所获得的苹果数（6）和第1行第2列所获得的苹果数（13），这两者哪个更大，谁大就取谁的值，显然第1行第2列所获得的苹果数（13）更大，所以用13加上第2行第2列的苹果数3 = 16，就是到达第2行第2列能获得的最大苹果数。同理，填所在格能获得的最大苹果数就是看它左面一格和上面一格哪个值更大，就取哪个值再加上自己格子里面的苹果数，就是到达此格能获得的最大苹果数。依此填完所有格子，最后得到下图：

技术分享

所以：到达右下角能够获得的最大苹果数量是76。所经过的路径可以通过倒推的方法得到，从右下角开始看所在格子的左边一格和上面一格哪边大就往哪边走，如果遇到一样大的，任选一条即可。

这样我们可以画出路线图，如下图右边表格：

技术分享

这个例子的分析和解决方法大概就是这样了。在前面第一个例子里面我们提到：空间换时间是动态规划的精髓。但是一个问题是否能够用动态规划算法来解决，需要看这个问题是否能被分解为更小的问题（子问题）。而子问题之间是否有包含的关系，是区别动态规划算法和分治法的所在。一般来说，分治法的各个子问题之间是相互独立的，比如折半查找（二分查找）、归并排序等。而动态规划算法的子问题在往下细分为更小的子问题时往往会遇到重复的子问题，我们只处理同一个子问题一次，将子问题的结果保存下来，这就是动态规划的最大特点。

动态规划算法总结起来就是两点：

1 寻找递推（递归）关系，比较专业的说法叫做状态转移方程。

2 保存中间状态，空间换时间。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SeqListSort
{
    /// <summary>
    /// <ather>
    /// lihonglin
    /// </ather>
    /// <content>
    /// 平面上有N*M个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始，每一步只能向下走或是
    /// 向右走，每次走到一个格子上就把格子里的苹果收集起来，这样一直走到右下角，你最多能收集到多少个苹果。
    ///输入：
    ///第一行输入行数和列数
    ///随机产生每个格子的中的苹果的数量
    ///输出：最多能收到的苹果的个数。
    ///
    ///思路分析:这是一个典型的二维数组DP问题
    ///基本状态：当你到达第x行第y列的格子的时候，收集到的苹果的数量dp[x,y]。
    ///转移方程：由于你只能向右走或者向下走，所以当你到达第x行第y列的格子的时候，你可能是从第x-1行第
    ///y列或者第x行第y-1列到达该格子的，而我们最后只要收集苹果最多的那一种方案。
    ///所以：dp[x,y] = max( if(x>0) dp[x-1,y] , if(y>0) dp[x,y-1])
    /// </content>
    /// </summary>
    class Apple_DP
    {
        static int[,] a = new int[100,100];
        static int[,] dp = new int[100,100];
        static int m,n;
 
        static void CollectApple(int x,int y)
        {
            dp[x, y] = a[x, y];
            int max = 0;
            if (x > 0 && max < dp[x - 1, y])// 上边一格 终点是x,y
            {
                max = dp[x - 1, y];
            }
            if (y > 0 && max < dp[x, y - 1])// 左边一格 终点是x,y
            {
                max = dp[x, y - 1];
            }
            dp[x, y] += max;
            if(x < m - 1)
            {
                CollectApple(x + 1, y);
            }   
            if(y < n - 1)
            {
                CollectApple(x, y + 1);
            }
        } 
 
        public static void InitMap()
        {
            Console.WriteLine("请输入m行，n列");
            m = Convert.ToInt32(Console.ReadLine());
            n = Convert.ToInt32(Console.ReadLine());
            Random r = new Random();
            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    //a[i,j] = r.Next(1,m + n);
                    Console.Write("{0,-3}", a[i, j] = r.Next(1, m + n));
                }
                Console.WriteLine();
            }
            CollectApple(0, 0);
            // 打印结果
            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    Console.Write("{0,-3}", dp[i, j]);
                }
                Console.WriteLine();
            }
        }
    }
}