[数据结构与算法]动态规划学习总结

本文结合 代码随想录 + leetcode官方解答，做了学习和总结，仅个人记录学习。

代码随想录网址代码随想录

动态规划大致分为以下几个问题：

1.基础动态规划

2.背包问题

3.打家劫舍

4.股票问题

5.子序列问题

1.基础动态规划

基础使用场景：多为计算最少个数，返回一般为一个整数
解决基本思路：
1考虑前一个状态和该状态的影响关系（递推公式）
2注意起始状态（初始化）
3考虑遍历时需要的基础存储量（如数组，变量），决定了循环的层数

2.背包问题

2.1? ? 01背包问题

2.1.1基础背包问题

问题：背包总承重量、物品重量+物品价值，每个物品最多取1次，求背包装载最大价值。
解法：二维数组，dp[i][j],i表示物品，j表示0-m（m为背包承受的最大重量），dp[i][j]表示j重量下前? ? ? ? ? i?个物品所能达到的最大价值。
? ? ?横向遍历：前i个物品所能装载到该重量下的最大价值。
? ? ?赋值：第i个物品在j重量下只有两个状态，要么装要么不装，所以只用对两个值比较选最大
? ? ? ? ? ? ? ? 不装：为dp[i-1][j]的值
? ? ? ? ? ? ? ? 装：为dp[i-1][j-w]的值
? ? ? ? ? ? ? ? 比较后取最大值。
? ? ?结果：取dp[i][j]

eg.）

?2.1.1变种背包

问题：从数据集中选出部分数，使这些数总和达到某个值n，数据集中的每个数最多取1次。
解法：二维数组，dp[i][j],i表示数字，j表示0-n（n为到达值），dp[i][j]表示j数值下前i个数是否能

? ? ? ? ? ?到达该值，为bool。
? ? ? ? ? ?关键不同点为dp[i][j]为bool值，核心为是否能到达这个值。
? ? ? ? ? ?判断方式和01背包相同，要么取值，要么不取值。
? ? ? ? ? ? ? ? ? ? ? 即 取：dp[i-1][j-n[I]]为true，则为true
? ? ? ? ? ? ? ? ? ? ? ? ? ?不取：dp[i-1][j]为true，则为true

?优化：

    dp[0] = true
    for _, weight := range stones {
        for j := m; j >= weight; j-- {
            dp[j] = dp[j] || dp[j-weight]
        }
    }

?

?

?