题解 | #三角形最小路径和#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param triangle int整型vector<vector<>> 
     * @return int整型
     */
    int minTrace(vector<vector<int> >& triangle) {
        // write code here
        int len = triangle.size(), i,j;
        int ans[len][len];
        for(i=0;i<len;i++)
        {
            for(j=0;j<=i;j++)
            {
                ans[i][j]=triangle[i][j];    
            }
        }
        for(i=1;i<len;i++)
        {
            for(j=0;j<i;j++)
            {
                ans[i][j]+=ans[i-1][j];
                if(j>=1)
                {
                    ans[i][j] = min(ans[i][j],triangle[i][j]+ans[i-1][j-1]);
                }
            }
            ans[i][j]+=ans[i-1][j-1];
        }
        int res = ans[len-1][0];
        for(j=1;j<i;j++)
        {
            res = min(res, ans[len-1][j]);
        }
        return res;
    }
};