动态规划是什么
动态规划是一种常用于解决具有重叠子问题和最优子结构性质的问题的算法设计技术。它通常用于优化问题，其中问题的解决方案可以被分解为更小的子问题，这些子问题可能会重复出现。动态规划的核心思想是将中间结果存储起来，以避免重复计算，从而提高效率。
就我个人的理解，动态规划是经典的“以空间换时间”的思维方式，将遍历问题中重复的部分优先算出，并记录下来，用于之后的计算。
动态规划在解决许多问题中都非常有用，例如背包问题、最短路径问题、编辑距离问题、斐波那契数列计算等。它是一个强大的算法工具，能够高效地解决多种优化问题，但需要合理定义问题的子问题和状态转移方程。
背包问题是什么
背包问题是可以用动态规划解决的一类经典经典的组合优化问题，通常用于描述如何在给定的资源限制下选择物品，以最大化其价值或效益。这个问题的常见形式有两种：01背包问题和完全背包问题。下面我们来看个例子。
题设：背包体积为V，n件物品，体积分别为[v0,v1,v2,…vn-1]，价值为[w0,w1,w2,…wn-1]
01背包问题：每个物品只能放一次
完全背包问题：每个物品可以放无限次
可能会求最值问题：
求必须放满背包的最大价值
求不必放满背包的最大价值
也可能会求
装满这个背包，有多少种办法
再细分为方法数是排列还是组合
最值问题的解决思路
背包问题中的最值问题一般指的是最大值问题，我们再把题目描述一下。
假设我们是一个登山家，能背的背包大小有限，背包体积为V。现在我们不能携带所有的登山物品，只能有选择性的带，总共n件物品，体积分别为[v0,v1,v2,…vn-1]，价值为[w0,w1,w2,…wn-1]，要怎么带才能在不超过背包体积的前提下，带上的物品价值最大呢？
初始化：设dp01[j] 为 放满体积为j的背包的最大价值
状态转移方程：（也可以理解为推导公式）dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]); i是n件物品的下标。
怎么理解这个方程呢，Math.max(dp[j], dp[j - v[i]] + w[i]) 也就是在dp01[j] 和 dp[j - v[i]] + w[i] 中取最大值，也就是说 尝试将物品i放入背包中，看看最大价值会不会更高？ 因为物品所占用的体积是v[i]，所以物品i放入背包前，背包需要空闲出所需的体积，也就是j - v[i]，此时背包的价值为dp[j - v[i]]，那么放入物品i后，背包的价值就是 dp[j - v[i]] + w[i] 了。
在实际的动态规划计算中：
-
创建一个一维数组dp[]，其中dp[j]表示在n个物品中选择，且背包容量为j时可以获得的最大总价值。
-
从第一个物品开始，依次考虑每个物品。
-
对于每个物品i，从右向左遍历dp数组，逐个更新dp数组的值：
- 此时，需要比较两种选择：
- 选择将物品i放入背包，这时总价值为 w[i] 加上剩余容量dp[j - v[i]] 时的最大价值，即 dp[j - v[i]] + w[i]。
- 不选择物品i，总价值为上一次迭代时dp[j]的值。
- 在这两种选择中，选择总价值更大的那个：Math.max(dp[j], dp[j - v[i]] + w[i])。
- 此时，需要比较两种选择：
-
继续处理下一个物品，直到处理完所有物品。
-
最终,dp[v]就是问题的最优解，表示在n个物品中选择，且背包容量为v时可以获得的最大总价值
其中01背包和完全背包与遍历顺序有关
放满背包与初始化值有关
设 01背包问题不放满为dp01
01背包问题必放满为dp02
完全背包问题不放满为dp11
完全背包问题必放满为dp12
我们将这四种场景写到同一段JAVA代码中，看看有啥区别
|
//>>>>>>>>>>>01背包>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> |
可以看出最大的区别在于 完全背包计算中，遍历背包是正序的，而01背包的遍历背包是倒序的。
背包问题常常需要两层for循环遍历，一层遍历物品，一层遍历背包（也就是体积），我们通常先遍历物品再遍历背包（其中原因不赘述，有兴趣可以搜索下）。在01背包问题中，先遍历物品，再倒序遍历背包，选择从右向左遍历的原因是为了避免当前物品的选择对之后的物品造成影响。这是因为01背包问题的特性决定了每个物品只能选择放入背包一次或不放入，因此在更新dp数组时，我们需要确保之前的物品选择与之后的物品选择不会相互影响。
读者可以尝试下01背包问题下，正序遍历，看看会发生什么，加深自己的理解。
