【动态规划】Leetcode---Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

思路：
假设第m行，n列的最小值为fun（m，n），其中m>=0, n>=0, 第m行元素个数为number，那么：
if(m==0){
    fun(m,n)=value(m,n)
}
else{
    if(n!=0 && n!=number-1)
        fun(m,n)=min{fun(m-1,n), fun(m-1,n-1)}+value(m,n);
    else
        fun(m,n)=fun(m-1,n)+value(m,n);
}
所以，我们找到了状态转移方程，编程如下：
    int minimumTotal(vector > &triangle) {
        int min=0xFFFFFFFF;
        int mnum=triangle.size();
        int num=triangle[triangle.size()-1].size();
        for(int i=0;i             int result = fun(mnum-1,i,triangle);
            if(min>result)
                min=result;
        }
        return min;
    }
    int fun(int m, int n, vector > &triangle){
        int number=triangle[m].size();
        if(m==0){
            return triangle[0][0];
        }
        else{
            if(n!=0 && n!=number-1)
                return min(fun(m-1,n,triangle), fun(m-1,n-1,triangle))+triangle[m][n];
            else
                return fun(m-1,n,triangle)+triangle[m][n];
        }
    }
但是运行结果是想想原因，就是递归导致了很多重复的操作，按照动态规划的基本原理，可以把递归的结果存起来，然后查表。
动态规划常常适用于有和性质的问题
最优子结构，我的理解，就是问题的解可以通过子问题的解来描述，也就是递归。
重叠子问题，我的理解，就是要是直接用递归的话，很多问题是重复的，所以需要查表，节省时间。分治法就不是，它不需要重复去调用一些递归。
对于上面的题目来说，它需要做的事情就是把结果存起来，存在哪里呢？
可以存在一个全局变量里，也可以存在triangle里。下面是新的解法：

    int minimumTotal(vector > &triangle) {
        int m_number=triangle.size();
        for(int m=0;m             int n_number=triangle[m].size();
            for(int n=0;n                 if(m>0){
                    if(n!=0 && n!=n_number-1)
                        triangle[m][n]= min(triangle[m-1][n], triangle[m-1][n-1])+triangle[m][n];
                    else
                        triangle[m][n]= triangle[m-1][n]+triangle[m][n];
                }
            }
        }
        int result=triangle[m_number-1][0];
        for(int i=1;i             if(result>triangle[m_number-1][i])
                result=triangle[m_number-1][i];
        }
        return result;
    }