lintcode::min_path_sum::Solution类 参考

#include <lintcode.h>

静态 Public 成员函数
static int	minPathSum (vector< vector< int > > &grid)

详细描述

在文件 lintcode.h 第 129 行定义.

成员函数说明

minPathSum()

int lintcode::min_path_sum::Solution::minPathSum ( vector< vector< int > > &  grid )

static

参数

grid	a list of lists of integers

返回

: An integer, minimizes the sum of all numbers along its path

在文件 lintcode.cpp 第 248 行定义.

                                                          {
            const unsigned int m = grid.size();
            const unsigned int n = grid[0].size();
            auto *dp             = new int *[m + 1];
            for(int i = 0; i <= m; i++) {
                dp[i] = new int[n + 1];
                memset(dp[i], INT_MAX, (n + 1) * sizeof(int));
            }
            dp[1][1] = grid[0][0];
            for(int i = 1; i <= m; i++) {
                for(int j = 1; j <= n; j++) {
                    if(i == 1 && j == 1) {
                        continue;
                    }
                    unsigned int min = dp[i - 1][j];
                    if(dp[i][j - 1] < min) {
                        min = dp[i][j - 1];
                    }
                    dp[i][j] = grid[i - 1][j - 1] + min;
                }
            }
            const auto ans = dp[m][n];
            for(int i = 0; i <= m; i++) {
                delete[] dp[i];
            }
            delete[] dp;
            return ans;
        }

---

该类的文档由以下文件生成:

• lintcode.h
• lintcode.cpp