动态规划处理与优化其核心算法

动态规划中的背包问题

• 1. 背包问题的基本介绍
• 2. 0-1背包问题的描述
• • 2.1 0-1背包问题的模板设计

• 2.2 数组等和分割的问题

• 2.3 最后一块石头重量的问题 II

• 2.4 目标和（*）

• 2.5 一与零的问题

• 3 多件物品数量限制的背包问题

• 31 多件物品数量限制的背包实现方案

• 32 货币面额转换（子集求和问题）

• 33 子集求和（IV）

• 34 货币面额转换

• 35 平方数组成的数

• 36 字符串分割(*)

  • 4. 多重背包问题

基于动态规划的方法是一种高阶算法技术，在解决优化问题时展现出强大的能力。这种方法的特点在于每个阶段的状态都必然是从前一阶段的状态演变而来，在此过程中需要遵循严格的递推关系。这种模式与贪心算法不同，在后者中直接从局部选择最优解而无需考虑全局情况。其中最为著名的是背包问题这一经典案例，在此之外它还能解决众多实际应用问题。例如我们可以列举一系列可以利用动态规划方法进行建模和求解的实际案例（题目源自leetcode题库中的经典题集以及Code Structure等资源）。

1.背包问题概述

背包问题的分类主要依据同一物品的数量变化而产生差异的情况，请参