LeetCode120-"最短路径"-C#实现

leetcode

题目: https://leetcode.com/problems/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.

Subscribe to see which companies asked this question

分析

• 题意:　从 三角形顶端到底部经过的点的和的最小值(例子: 2-3-5-1)
• 注意: 每次只能走与之相邻的点
• 动态规划
• 状态:
  构造与三角形一模一样的dp[][], dp[i][j] 表示道[i][j]点的路径的和

• 初始化:

• 状态转移:

    if (j == 0)//在最左边
        dp[i][j] = dp[i - 1][j] + triangle[i][j];
    else if (j == triangle[i].Count - 1)//在最右边
        dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
    else//在中间
        dp[i][j] = Math.Min(dp[i - 1][j -1 ], dp[i - 1][j]) + triangle[i][j];

• 结果
  

  最后一行dp的最小值

代码

public class Solution
{
    public int MinimumTotal(IList<IList<int>> triangle)
    {
        if (triangle.Count == 0) return 0;
        int[][] dp = new int[triangle.Count][];
        for(int i=0; i<triangle.Count; i++)
        {
            dp[i] = new int[triangle[i].Count];
            for (int j = 0; j < triangle[i].Count; j ++)
            {
                if (i > 0)
                {
                    if (j == 0)
                        dp[i][j] = dp[i - 1][j] + triangle[i][j];
                    else if (j == triangle[i].Count - 1)
                        dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                    else
                        dp[i][j] = Math.Min(dp[i - 1][j -1 ], dp[i - 1][j]) + triangle[i][j];
                }
                else { dp[i][j] = triangle[i][j]; }
            }
        }
        return dp[triangle.Count - 1].Min();
    }
}