Leetcode topic -- 120 Minimum length sum of triangles, simple DP

Topic link

120. The minimum path of a triangle and - Power button （LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/triangle/

Don't think about doing this with greed ！ Greedy code is not only long , And it's easy to make mistakes . Besides, this is a dp The template questions , You don't even have to push the equation , I'm sure I don't even want to directly dp 了

Pay attention to some points. ：

1、dp From the top down , But the title says from bottom to top , When writing recursion, don't get it upside down

 2、 Pay attention to the limited array size and data range .

in addition , The main function input of this problem is also very interesting , I wrote it for you , I hope to share with you

// The minimum path of a triangle and 
int minimumTotal(vector<vector<int>>& triangle) {
    int len = triangle.size();
    if (len == 1)
    {
        return triangle[0][0];
    }
    int dp[100][100] = { 0 };
    int ans = 0;
    int i = 0;
    dp[0][0] = triangle[0][0];
    for (int i = 1; i < len; i++)
    {
        for (int j = 0; j < triangle[i].size(); j++)
        {
            if (j - 1 >= 0 && j < triangle[i - 1].size())
            {
                dp[i][j] = triangle[i][j] + min(dp[i - 1][j], dp[i - 1][j - 1]);
            }
            else if(j - 1 < 0)
            {
                dp[i][j] = triangle[i][j] + dp[i - 1][j];
            }
            else 
            {
                dp[i][j] = triangle[i][j] + dp[i - 1][j - 1];
            }
        }
    }
    int minn = 100000;
    for (int i = 0; i < len; i++)
    {
        minn = min(minn, dp[len - 1][i]);
    }
    return minn;
}

int main()
{
    vector<vector<int>>tr;
    int n = 1;
    for (int i = 0; i < 3; i++)
    {
        vector<int>ret;
        for (int j = 0; j < n; j++)
        {
            int a = 0;
            cin >> a;
            ret.push_back(a);
        }
        tr.push_back(ret);
        ret.clear();
        n++;
    }
    int ans = minimumTotal(tr);
    cout << ans;
    return 0;
}