算法刷题笔记 (16) 最小路径和 组合总和 子集 不同路径

最小路径和

最小路径和

解题思路

利用动态规划，dp[i][j]表示总左上角到grid[i][j]的最小路径和。其中：

• dp[0][0] = grid[0][0]
• dp[i][0] = dp[i-1][0] + grid[i][0]
• dp[0][j] = dp[0][j-1] + grid[0][j]
• dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

解题代码

func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    // 定义dp数组
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    dp[0][0] = grid[0][0]
    // 初始化dp数组，初始化dp[i][0]、dp[0][j]
    for i := 1; i < m; i++ {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }
    for j := 1; j < n; j++ {
        dp[0][j] = dp[0][j-1] + grid[0][j]
    }
    // 计算dp数组
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        }
    }

    return dp[m-1][n-1]
}

func min(n1, n2 int) int {
    if n1 < n2 {
        return n1
    } else {
        return n2
    }
}

组合总和

组合总和

解题思路

利用回溯算法

• 首先对candidates进行排序，使之递增有序
• 可以将结果看作一棵len(candidates)叉树，第i个分支对应选择candidates[i]，并且每次i从startIndex开始，这样可以避免重复结果

解题代码

func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)   // 排序
    res := make([][]int, 0)     // 记录结果
    path := make([]int, 0)         // 记录当前选择的数字
    var backtrack func(curSum int, startIntdex int)
    backtrack = func(curSum int, startIntdex int) {      // curSum表示当前数字之和，startIndex表示从startIndex开始遍历
        if curSum == target {
            // 等于目标值，加入结果集中
            temp := make([]int, len(path))
            copy(temp, path)
            res = append(res, temp)
        }
        // 重复选取candidates[curIndex]
        for i:= startIntdex; i < len(candidates); i++{
            if curSum+candidates[i] > target {
                break
            }
            path = append(path, candidates[i])   // 选取当前数字
            backtrack(curSum+candidates[i], i)
            // 恢复状态
            path = path[:len(path)-1]
        }
    }

    backtrack(0, 0)    // 执行回溯

    return res

}

子集

子集

解题思路

利用回溯算法，求所有的子集

解题代码

func subsets(nums []int) [][]int {
    res := make([][]int, 0)     // 结果集
    path := make([]int, 0)  // 记录已经选择的元素
    var backtrack func(startIndex int)
    backtrack = func(startIndex int) {  // startIndex为待选择的数字下标
        temp := make([]int, len(path))
        copy(temp, path)
        res = append(res, temp)     // 将path加入结果集
        
        for i := startIndex; i < len(nums); i++ {
            path = append(path, nums[i])    // 选择nums[i]
            backtrack(i+1)
            // 恢复状态
            path = path[:len(path)-1]
        }
    }

    backtrack(0)    // 执行回溯函数

    return res
}

不同路径

不同路径

解题思路

利用动态规划，记网格为grid[i][j]，dp[i][j]表示到达grid[i][j]的路径条数。

故对于dp的初始化：

• dp[i][0] = 1
• dp[0][j] = 1

对他dp的更新：

• dp[i][j] = dp[i-1][j] + dp[i][j-1]

解题代码

func uniquePaths(m int, n int) int {
    // 声明dp数组
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    // 初始化dp数组
    dp[0][0] = 1
    for i := 1; i < m; i++ {    // 初始化dp[i][0] = 1
        dp[i][0] = 1
    }
    for j := 1; j < n; j++ {    // 初始化dp[0][j] = 1
        dp[0][j] = 1
    }
    // 求dp数组
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }

    return dp[m-1][n-1]
}