硬撸动态规划

礼物说 2023-06-25 ⏳1.7分钟(0.7千字)

现在的面试越来越卷了，算法又绕不开动态规划。本文诣在记录下挑战动态规划，从easy到hard。本文参考动态规划详解,该文章已经写的很好了，本文就简单带过一些基础概念。

动态规划问题的一般形式就是求最值,比如说让你求最长递增子序列呀，最小编辑距离呀等等。核心问题就是穷举。而动态规划的穷举大都存在重叠子问题.所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。只有列出正确的「状态转移方程」才能正确地穷举。

用通俗易懂的方式说，就是我们需要通过前n-1个的结果去推算出第n个的结果，这就是「状态转移方程」

斐波那契数列

func fib(n int) int {
    dp := make([]int,n+2)
    dp[0]=0
    dp[1]=1
    for i:=2;i<=n;i++{
        dp[i]=(dp[i-1]+dp[i-2])%(1e9+7)
    }
    return dp[n]
}

状态转移方程就是 dp[i] = dp[i-1] + dp[i-2]，dp[i]的结果就是dp[i-1]与dp[i-2]之和。

凑零钱

func coinChange(coins []int, amount int) int {
    dp := make([]int,amount+1)
    dp[0] = 0
    for i:=1;i<=amount;i++{
        dp[i] = -1
        for _,coin := range coins {
            if i-coin >= 0 &&
                dp[i-coin] != -1 &&
                (dp[i-coin]+1 < dp[i] || dp[i] == -1){
                dp[i] = dp[i-coin]+1
            }
        }
    }
    
    return dp[amount]
}

状态转移方程就是 dp[i] = min(dp[i-coin[x]])+1 eg：假设硬币有1，2，5，那dp[7]的值就是dp[7-1],dp[7-2],dp[7-5]中的最小值+1.

最长递增子序列

func lengthOfLIS(nums []int) int {
    dp := make([]int,len(nums))
    for k,_ := range dp {
        dp[k] = 1
    }
    for i:=0;i<len(nums);i++{
        for j:=0;j<i;j++{
            if nums[i] > nums[j] && dp[j]+1 > dp[i]{
                dp[i] = dp[j]+1
            }
        }
    }
    fmt.Println(dp)
    max  := dp[0]
    for _,v := range dp {
        if v > max {
            max = v
        }
    }
    return max
}

状态转移方程就是 dp[i] = max(dp[i-x])+1 需满足nums[i-x] > nums[i] eg:dp[i]的值就是dp[1]-dp[i-1]之中，满足num[x]<num[i]的最大值+1.

最大子数组和

func maxSubArray(nums []int) int {
    dp := make([]int,len(nums))
    copy(dp,nums)
    for i :=1;i<len(nums);i++{
        if dp[i-1] > 0 {
            dp[i] = dp[i]+dp[i-1]
        }
    }
    
    max := nums[0]
    for _,v := range dp {
        if v > max {
            max = v
        }
    }
    return max
}

状态转移方程就是 dp[i] = max(nums[i],nums[i]+dp[i-1])，dp[i]代表包含自己的最大值.获取最大子数组和则遍历dp数组获取最大值。

编辑距离

最长公共子序列

func longestCommonSubsequence(text1 string, text2 string) int {
        dp := make([][]int, len(text1)+1)
        for k := range dp {
                dp[k] = make([]int, len(text2)+1)
        }

        for k1, v1 := range text1 {
                for k2, v2 := range text2 {
                        if v1 == v2 {
                                dp[k1+1][k2+1] = dp[k1][k2] + 1
                        } else {
                                if dp[k1+1][k2] > dp[k1][k2+1] {
                                        dp[k1+1][k2+1] = dp[k1+1][k2]
                                } else {
                                        dp[k1+1][k2+1] = dp[k1][k2+1]
                                }
                        }
                }
        }
        return dp[len(text1)][len(text2)]
}

比较典型的二维动态规划，状态转移方程就是如果相等则dp[i][j]=dp[i-1][j-1]+1否则dp[i] = max(nums[i][j-1],nums[i-1][j])

背包问题

416. 分割等和子集

func canPartition(nums []int) bool {
        var sum int
        for _, num := range nums {
                sum += num

        }
        if sum%2 != 0 {
                return false
        }

        value := sum / 2

        dp := make([][]bool, len(nums))
        for k := range dp {
                dp[k] = make([]bool, value+1)
        }

        for i := 0; i < len(nums); i++ {
                if nums[i] <= value {
                        dp[i][nums[i]] = true
                }
                if i == 0 {
                        continue
                }
                for j := 1; j <= value; j++ {
                        if dp[i-1][j] {
                                dp[i][j] = true
                        }

                        if dp[i-1][j] && j+nums[i] <= value {
                                dp[i][j+nums[i]] = true
                        }
                }
        }
        return dp[len(nums)-1][value]
}

本质上可以转化为数组元素之和能否能组成sum/2,可以通过二维动态规划来完成。dp[value][weight]是否为true取决于上一层的dp[value-1][weight]是否为true或者上一层的dp[value-1][weight-value]是否为true

零钱兑换

func coinChange(coins []int, amount int) int {
    dp := make([]int,amount+1)
    dp[0] = 0 
    for i:=1;i<=amount;i++{
        dp[i] = -1
        for _,coin := range coins {
            if i-coin < 0 {
                continue
            }
            c := dp[i-coin]
            if c == -1 {
                continue
            }
            if dp[i] == -1 || dp[i] != -1 && c+1 < dp[i]  {
                dp[i] = c+1
            }
        }
    }
    return dp[amount]
}

零钱兑换2

func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
    for _, coin := range coins {
        for i := coin; i <= amount; i++ {
            dp[i] += dp[i-coin]
        }
    }
    return dp[amount]
}