题解 | #三角形最小路径和#
三角形最小路径和
https://www.nowcoder.com/practice/c9d44b73dc7c4dbfa4272224b1f9b42c
#include <climits>
class Solution
{
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型vector<vector<>>
* @return int整型
*/
int minTrace(vector<vector<int> >& triangle)
{
int m = triangle.size();
vector<vector<int>> dp(m + 1, vector<int>(m + 1, INT_MAX));
dp[0][0] = dp[0][1] = 0;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= i; j++)
{
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i - 1][j - 1];
}
}
int ret = INT_MAX;
for (int i = 1; i <= m; i++)
{
ret = min(ret, dp[m][i]);
}
return ret;
}
};
投递快手等公司10个岗位