动态规划是一种重要的算法思想，常用于解决复杂问题的优化，特别是在有限资源的分配或路径规划等问题上。在“动态规划入门第3课”的内容中，我们主要探讨了两个经典的问题：背包问题和寻找数列分割使得两堆和的差距最小。
我们来看背包问题。这是一个经典的0-1背包问题，其中涉及到N个物品，每件物品都有自己的体积（或重量）和价值。我们需要将这些物品放入一个容量为W的背包中，目标是最大化背包中物品的总价值。动态规划在此问题中的应用是通过构建一个二维数组dp[i][w]，其中i表示当前考虑第i个物品，w表示背包的剩余容量。dp[i][w]表示前i个物品中选取若干个，且总重量不超过w的情况下，能够获得的最大价值。我们可以通过递推公式更新这个数组，即dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)，其中wi和vi分别是第i个物品的重量和价值。dp[N][W]就是我们要求的最大价值。
接下来，我们讨论了第二个问题，即如何将n个整数分成两堆，使得两堆的和尽可能接近。这个问题可以转换为求解两堆数的差距最小值。动态规划在这里的思路是，从总和的一半开始，逐渐向下搜索，判断每个数是否可以用序列中的数来组成。对于每个可能的和，我们检查序列中是否存在这样的组合，如果存在，那么总和与当前和之间的差值就是可能的最小差距。我们可以维护一个最小差距记录，随着遍历的进行不断更新，最终得到最小差距。
在实际编程实现时，为了方便处理正负数，可以将数组的下标进行偏移，如将正数的下标从20000开始，负数的下标从0开始，这样可以避免负数下标的困扰。
动态规划是一种通过逐步构建最优解的方法，它通过将大问题分解成小问题并存储子问题的解，避免了重复计算，从而提高了效率。在上述两个问题中，我们看到了动态规划如何通过构建状态转移方程和利用记忆化存储来解决复杂问题，这为我们处理类似问题提供了有效的工具和思路。在学习动态规划的过程中，理解问题的结构、定义合适的状态和状态转移方程是关键步骤。
