三角形

class Solution {
public:
    //从下往上找，不使用额外空间，缺点是修改了输入
    int minimumTotal(vector<vector<int> > &***) {
        for(int i=***.size()-2;i>=0;--i){
            for(int j=0;j<***[i].size();++j){
                ***[i][j]+=min(***[i+1][j],***[i+1][j+1]);
            }
        }
        return ***[0][0];
    }
    
    //使用O(n)的额外空间，不修改原输入
    int minimumTotal(vector<vector<int> > &***) {
        vector<int> res(***.back());
        for(int i=***.size()-2;i>=0;--i){
            for(int j=0;j<***[i].size();++j){
                res[j]=***[i][j]+min(res[j],res[j+1]);
            }
        }
        return res[0];
    }
};

import java.util.*;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
		for (int i = ***.size() - 2; i >= 0; i --) {
			for (int j = 0; j < ***.get(i + 1).size() - 1; j ++) {
				int min = Math.min(***.get(i + 1).get(j), ***.get(i + 1).get(j + 1));
				***.get(i).set(j, ***.get(i).get(j) + min);
			}
		}
		return ***.get(0).get(0);
	}
}

class Solution {
public:
    int minimumTotal(vector<vector<int> > &***) {
        int i,j;
        for(i=***.size()-2;i>=0;--i)
        {
            for(j=0;j<i+1;++j)
            {
                ***[i][j]=***[i][j]+((***[i+1][j]>***[i+1][j+1])?***[i+1][j+1]:***[i+1][j]);
            }
        }
        return ***[0][0];
    }
};

// 给定一个三角形，找出从顶到底的最小路径和，每一步可以从上一行移动到下一行相邻的数字
//    [                    
//         [2],                 [2],               
//        [3,4],              [3, 4],            [2],
//       [6,5,7],      ==>   [7, 6, 10]     ==>  [9, 10]   ==>     [11]
//      [4,1,8,3]
//    ]

/**思路: 
    * 自底向上 dp: 不需要额外的空间 
    * dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + ***[i][j]
    * dp[i][j]: 表示到达 (i, j)最小路径的总和 
*/

// 修改输入样例:
//    4

//    2
//    3 4
//    6 5 7
//    4 1 8 3 

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;


class Solution {
public:
    int minimumTotal(vector<vector<int> > &***) {
        int n = ***.size();
        for(int i = n - 2; i >= 0; i--) {
            for(int j = 0; j <= i; j++) {
                ***[i][j] += min(***[i+1][j], ***[i+1][j+1]);    
            }
        }
        return ***[0][0];
    }
};

int main()
{
    ifstream infile("in.txt", ifstream::in);
    #define cin infile
    vector<vector<int> > ***;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        vector<int> vi(i+1, 0);
        for(int j = 0; j < i+1; j++)
            cin >> vi[j];
        ***.push_back(vi);
    }
    Solution* s = new Solution();
    cout << s->minimumTotal(***) << endl;
    return 0;
}

import java.util.ArrayList;
/*
可以发现一个规律：第l个数组的第k个元素的下一个元素的有两种可能，分别是第l+1个数组的第k个元素与第k+1个元素。所以递归取最小值搞定
*/
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
        int sum ;
        sum = getResult(***,0,0);
        return sum;
    }
    public int getResult(ArrayList<ArrayList<Integer>> ***,int l,int k) {
        int sum = ***.get(l).get(k);
        if(l<***.size()-1)
             sum = sum+Math.min(getResult(***,l+1,k),getResult(***,l+1,k+1));
        return sum;
    }
}

// 贴一个二叉树的思路。

/**
 *
 * 整个三角形可以看做一个二叉树，用f表示二叉树深度，从1到n。
 * 二维ArrayList<ArrayList<Integer>> 可以看做是一个一维数组，其中index表示数组的游标，从0到len-1。
 * 左孩子就是当前节点加上这层孩子的数目f，也就是index+f
 * len是一维数组，也可以用来约束一维数组的index是否越界，换句话，就是可以判断叶子节点。
 *
 */
public class Solution {
    int len;

    public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
        len = ***.size() * (***.size() + 1) / 2;
        return minSum(***, 0, 1);
    }

    /**
     *  用来表示某棵树的路径最小的节点之和，无非两种情况，选择左树或者右树
     */
    private int minSum(ArrayList<ArrayList<Integer>> ***, int index, int f) {
        if (index >= len) return 0;
        int leftVal = minSum(***, index + f, f + 1);   //左树的最小路径节点和
        int rightVal = minSum(***, index + f + 1, f + 1);  //右树的最小路径节点和

        List<Integer> list = ***.get(f - 1);   //获取层  数组
        int val = list.get(index - (f - 1) * f / 2);  //换算出在当前数组的位置，根据1...n的连续和公式，前f-1层一共有 (f-1)*f/2个节点

        return Math.min(leftVal + val, rightVal + val);
    }
}

class Solution {
public:
    int minimumTotal(vector<vector<int> > &***) {
        int len = ***.size();
        vector<int> dp(len, 0);
        for(int i = len-1; i >= 0; --i){
            for(int j = 0; j <= i; ++j){
                if(i == len-1){
                    dp[j] = ***[i][j];
                }else{
                    dp[j] = ***[i][j] + min(dp[j], dp[j+1]);
                }
            }
        }
        
        return dp[0];
    }
};

import java.util.ArrayList;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
        int size = ***.size();
        ArrayList<Integer> arr = ***.get(size - 1);
        for(int i = size - 2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                arr.set(j, Math.min(arr.get(j), arr.get(j + 1)) + ***.get(i).get(j));
            }
        }
        return arr.get(0);
    }
}

//从后往上
    public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
        if(***==null||***.size()==0)
            return 0;
        int[] dp=new int[***.size()];
        ArrayList<Integer> last= ***.get(***.size()-1);
        //最后一层复制给dp数组
        for(int i=0;i<last.size();i++)
            dp[i]=last.get(i);
        //最后第二层开始
        for(int i=***.size()-2;i>=0;i--){
            ArrayList<Integer> curList =***.get(i);
            //每个节点跟下一层两个节点进行比较
            for(int j=0;j<curList.size();j++)
                dp[j]=Math.min(curList.get(j)+dp[j],curList.get(j)+dp[j+1]);
        }
        return dp[0];
    }

/**
 * 方法：动态规划
 * 状态：
 *      子状态：从(0,0)到(1,0),(1,1),(2,0),...(n,n)的最短路径和
 *      F(i,j): 从(0,0)到(i,j)的最短路径和
 * 状态递推：
 *      F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
 * 初始值：
 *      F(0,0) = triangle[0][0]
 * 返回结果：
 *      min(F(n-1, i))
 *      最后一行最小的元素
 */

public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle == null) return 0;

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int row = triangle.size();
        for (int i = 0; i < row; i++) {
            result.add(new ArrayList<>());
        }
        // F[0][0]初始化
        result.get(0).add(triangle.get(0).get(0));
        for (int i = 1; i < row; i++) {
            //上一行的最小值
            int curSum = 0;
            for (int j = 0; j < triangle.get(i).size(); j++) {
                // 处理左边界和右边界
                if (j == 0) {
                    curSum = result.get(i - 1).get(0);
                } else if (j == i) {
                    curSum = result.get(i - 1).get(j - 1);
                } else {
                    curSum = Math.min(result.get(i - 1).get(j - 1), result.get(i - 1).get(j));
                }
                // F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
                result.get(i).add(curSum  + triangle.get(i).get(j));
            }
        }
        int size = triangle.size();
        // min(F(n-1, i))
        int allMin = result.get(size - 1).get(0);
        //在最后一行找最小的值
        for (int i = 1; i < result.get(size - 1).size(); i++) {
            allMin = Math.min(result.get(size - 1).get(i), allMin);
        }
        return allMin;
    }
}

import java.util.*;
class Solution {
    /**
     *  DP，复用一个长度triangle.size()大小的数组记录
     *  上一层元素的构成的小三角的最小路径和,状态转移方程
     *  f(i,j) = min(f(i+1, j)+triangle[i][j], f(i+1, j+1)+triangle[i][j])
     */
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if(triangle.size()<1) return 0;
        int[] min = new int[triangle.size()];
        for(int i=0; i<triangle.size(); i++){
            min[i] = triangle.get(triangle.size()-1).get(i);
        }
        for(int i=triangle.size()-2; i>=0; i--){
            for(int j=0; j<=i; j++){
                min[j] = Math.min(min[j]+triangle.get(i).get(j), 
                                  min[j+1]+triangle.get(i).get(j));
            }
        }
        return min[0];
    }
}

class Solution {
public:
    int minimumTotal(vector<vector<int> > &***) {
        int rows=***.size();
        int dp[rows][rows];
        dp[0][0]=***[0][0];
        for(int i=1;i<rows;i++){
            dp[i][0]=***[i][0]+dp[i-1][0];
            dp[i][i]=***[i][i]+dp[i-1][i-1];
        }
        for(int i=2;i<rows;i++){
            for(int j=1;j<i;j++)
                dp[i][j]=***[i][j]+min(dp[i-1][j-1],dp[i-1][j]);
        }
        int res=dp[rows-1][0];
        for(int i=1;i<rows;i++)
            res=min(res,dp[rows-1][i]);
        return res;
    }
};

class Solution {
public:
    int minimumTotal(vector<vector<int> > &***) {
        int* pDP = new int[***.size() + 1];
        for (int i = 0; i <= ***.size(); ++i)
            pDP[i] = INT_MAX;
        pDP[0] = ***[0][0];
        for (int i = 1; i < ***.size(); ++i)
        {
            for (int j = i; j >= 1; --j)
                pDP[j] = ***[i][j] + min(pDP[j - 1], pDP[j]);
            pDP[0] += ***[i][0];
        }
        int nMin = INT_MAX;
        for (int i = 0; i < ***.size(); ++i)
            if (nMin > pDP[i])
                nMin = pDP[i];
        delete[] pDP;
        return nMin;
    }
};

class Solution {
public:
    int minimumTotal(vector<vector<int> > &***) {
        if(***.empty())return 0;
        vector<int>dp(***.back().size());
        for(int j=0;j<(int)***.back().size();j++)dp[j]=***.back()[j];
        for(int i=(int)***.size()-2;i>=0;i--)
            for(int j=0;j<(int)***[i].size();j++)
                dp[j]=***[i][j]+min(dp[j],dp[j+1]);       
        return dp[0];
    }
};

//以某个节点为终点的最短路径，等于以该节点的各个前驱节点为终点的最短路径中
//最短的值，加上该节点的值
//状态转移方程 ：dist[j] = minval(dist[j],dist[j-1]) + ***(i,j); 
class Solution {
public:
    int minimumTotal(vector<vector<int> > &***) {
        int n = ***.size();
        int dist[n];        //空间复杂度O(n)
        dist[0] = ***[0][0];
        int mindist;
        for(int i = 2;i<=n;i++){
            for(int j=i-1;j>=0;j--){
                if(j==0) dist[j] = dist[0] + ***[i-1][j];
                else if(j==i-1) dist[j] = dist[j-1] + ***[i-1][j];
                else dist[j] = minval(dist[j],dist[j-1]) + ***[i-1][j]; //状态转移方程
            }
        }
        for(int k=0;k<n;k++){
            if(k==0) mindist=dist[0];
            else if(mindist > dist[k]) mindist = dist[k];
        }
        return mindist;
    }
    int minval(int a, int b){
        return a > b ? b : a;
    }
};

class Solution {
public:
    int minimumTotal(vector<vector<int> > &***) {
        int h = ***.size();         if (h == 1) { return ***[0][0]; }         ***[1][0] += ***[0][0];         ***[1][1] += ***[0][0];         for (int i = 2; i < h; i++)         {             ***[i][0] += ***[i - 1][0];             for (int j = 1; j < ***[i].size()-1; j++)             {                 int temp = ***[i - 1][j] < ***[i - 1][j - 1] ? ***[i - 1][j] : ***[i - 1][j - 1];
                ***[i][j]+=temp;             }             ***[i][i] += ***[i - 1][i-1];         }         int min = ***[h - 1][0];         for (int i = 1; i <= h-1; i++)         {             if (***[h - 1][i] < min) { min = ***[h - 1][i]; }         }         return min;
    }
};

/**
 * @Description DFS recursion 简单易懂。
 */
public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
    return DFS(***, 0, 0);
}
private int DFS(ArrayList<ArrayList<Integer>> *** , int i , int j) {
    return i == ***.size()-1？***.get(i).get(j):***.get(i).get(j)+ Math.min(DFS(*** , i+1 ,j), DFS(***, i+1 ,j+1));
}

import java.util.HashMap;
import java.util.ArrayList;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
        if (*** == null || ***.get(0) == null) {
            return 0;
        }
        //HashMap<String, Integer> record = new HashMap<String, Integer>(); 
        //return dfs2(***, 0, 0, record);
        return dp(***);
    }
    
    /**
    * 递归：
    * 自顶至下递归，用当前结点的值加上左右子结点（子路径）中较小的值
    *
    * 优点：简单易懂
    * 缺点：，记行数为n，递归深度约为2^n，存在大量的重复计算
    **/
    private static int dfs(ArrayList<ArrayList<Integer>> tri, int row, int col) {
        if (row >= tri.size()) {
            return 0;
        }
        int val = tri.get(row).get(col);
        return val + Math.min(dfs(tri, row + 1, col), dfs(tri, row + 1, col + 1));
    }
    
    /**
    * 改进版递归：
    * 利用map记录计算过的结点，减少重复工作
    *
    * 但这个方法不符合题意中空间复杂度O(n)的限制。
    **/
    private static int dfs2(ArrayList<ArrayList<Integer>> tri, int row, int col, HashMap<String, Integer> record) {
        if (row >= tri.size()) {
            return 0;
        }
        String key = new StringBuilder().append(row).append(" ").append(col).toString();
        if (record.containsKey(key)) {
            return record.get(key);
        }
        int val = tri.get(row).get(col);
        int min = val + Math.min(dfs2(tri, row + 1, col, record), dfs2(tri, row + 1, col + 1, record));
        record.put(key, min);
        return min;
    }
    
    /**
    * 动态规划：
    * 自底至上计算(因为这样可以减少重复的计算工作)
    * 在每一行中，计算每个结点加上左右子结点（子路径）中较小的值，并放入当前结点，
    * 然后，循环计算，直到顶点，最终的tri.get(0).get(0)即为所求结果。
    **/
    private static int dp(ArrayList<ArrayList<Integer>> tri) {
        for (int i = tri.size() - 2; i >= 0; i--) {
            for (int j = 0; j < tri.get(i).size(); j++) {
                tri.get(i).set(j, tri.get(i).get(j) + Math.min(tri.get(i + 1).get(j), tri.get(i + 1).get(j + 1)));
            }
        }
        return tri.get(0).get(0);
    }
    
}