数据结构与算法

常见算法思想8：动态规划法

2020-02-19  本文已影响0人  GoFuncChan

动态规划问题的分类

常见动态规划问题的类型

动态规划问题解决步骤

例题解析

一、求最值问题：

你有三种硬币，面值分别为2，5，7，每种硬币都有足够多。现在你需要买一本书需要27元，如何用最少的硬币组合正好付清，不需要对方找钱？

1.确定状态
2.转移方程
3.初始条件和边界情况
4.计算顺序
func CoinChange(coinList []int, total int) int {
    // 0,....,n : [n+1]
    // 0,....,n-1 : [n]
    stepList := make([]int, total+1) // 存储每1元需要多少枚硬币的结果
    coinNum := len(coinList)         // 硬币的类型数量

    // 初始条件
    stepList[0] = 0

    var i, j int
    for i = 1; i <= total; i++{

        // 每一元的情况需要多少枚硬币,默认设置无穷大
        stepList[i] = math.MaxInt64
        // 最后一枚硬币 stepList[j]
        // stepList[i]= math.Min(stepList[i-coinList[j]])+1,stepList[i])
        for j = 0; j < coinNum; j++ {
            // total需大于硬币面值
            if i >= coinList[j] && stepList[i-coinList[j]] != math.MaxInt64 {
                // 转移方程
                stepList[i] = int(math.Min(float64(stepList[i-coinList[j]])+1, float64(stepList[i])))
            }
        }
    }

    if stepList[total] == math.MaxInt64 {
        stepList[total] = -1
    }

    return stepList[total]

}

二、求计数：

给定m行n列的网格，有一个机器人从左上角(0,0)出发，每一步可以向下或者向右走一步，问有多少种不同的方式走到右下角。

1.确定状态
2.转移方程
3.初始条件和边界情况

4.计算顺序

// 输入行列参数m,n
func UniquePaths(m, n int) int{
    // 开一个二维数组m行,存储走到当前每一格的可能性步数
    f := make([][]int, m, m)

    var i, j int
    for i = 0; i < m; i++ { // row:top to bottom
        // 每行开n列的数组
        f[i] = make([]int, n, n)
        for j = 0; j < n; j++ { // column:left to right
            if i == 0 || j == 0 {
                // 初始格为1
                f[i][j] = 1
            }else {
                // 转移方程:当前格 = 上一格往下的情况 + 上一格往右的情况
                f[i][j] = f[i-1][j] + f[i][j-1]
            }
        }
    }

    // 只需返回最后一格作为结果即可
    return f[m-1][n-1]
}

三、求可能性：

有n块石头分别在x轴的0,1,...,n-1位置，一只青蛙在石头0，想跳到石头n-1，如果青蛙在第i块石头上，它最多可以向右跳距离ai，问青蛙能否跳到石头n-1？
例子：输入a=[2,3,1,1,4],输出true；输入a=[3,2,1,0,4],输出false;

1.确定状态
2.转移方程
3.初始条件和边界情况
4.计算顺序
func CanJump(list []int) bool {
    // 石头块数
    n := len(list)

    // 开辟数组,存储跳到每个石头的可能性
    canList := make([]bool, n, n)
    canList[0] = true // 初始位置0石头肯定可以

    // 从位置1开始
    for j := 1; j < n; j++ {
        canList[j] = false // 假设不可行

        // 从当前石头i开始
        // 最后一跳是i到j,j必须在i后面
        for i := 0; i < j; i++ {
            // 转移方程
            if canList[i] && i+list[i] >= j {
                canList[j] = true
                break
            }
        }
    }

    return canList[n-1]
}
上一篇 下一篇

猜你喜欢

热点阅读