学问思辨行: 记录生活学习和工作中的实践和思考，以期实现终身成长.

上一篇文章介绍了01背包问题及分析，这篇短文主要介绍一个有点不同的题目：完全背包问题。具体题目内容如下：有N种物品和一个容量是V的背包，每种物品都有无限件可用。第 𝑖 种物品的体积是𝑣𝑖，价值是𝑤𝑖。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。其中输入格式和样例等和上一篇文章一样，具体可以参考引文1链接。 问题分析：和01背包不同的是，每一种物体可以放多个（具体个数上限为V/v[i]）,从另一个角度灵活考虑，可以认为该问题可以转换为01背包问题。及一种物体可以看成是V/v[i]种不同的物体，但其价值相同。通过这样转换后完全背包问题就可以转化为01背包问题。转换的代码如下所示。其中dp_solver的递推计算和01背包中国的代码段是一样的。 下面的思路提供一种更简洁的实现，具体的状态转移方程有一定的变化，即当j>v[i]的时候，可以放入1到j/v[i]个物体，因此状态转移方程写为： dp[i][j] = max(dp[i-1][j-m*v[i]]+m*w[i], dp[i-1][j])（其中m=1,2,…j/v[i]） 具体代码如下(dp[1][j]的定义也有变化)： References

从这篇短文开始将准备陆续介绍一下动态规划中的背包问题，这次主要介绍01背包问题的求解方法及分析。所谓01背包问题，就是N个物体中每一个物体要么不放入背包（0状态），要么一个物体要完整的放入背包（1状态）。具体问题描述如下。 有 N件物品和一个容量是 V的背包。每件物品只能使用一次。第 i件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。输出格式输出一个整数，表示最大价值。数据范围0<N,V≤1000，0<vi,wi≤1000输入样例4 51 22 43 44 5输出样例：8 分析：我们可以看出，每个物体要么放入（状态为1），要么不放（状态为0）有两种状态，N种物体会有2的N次幂种状态（当然有些状态会不满足条件，如总容量超标），用这种组合枚举的方式计算量会比较大（算法复杂度）。下面就用深度优先搜索的方式去向大家介绍此种方法的实现。首先我们贴上代码如下： 上述代码的浅析过程如下：第一个参数idx表示已经从第一个物体搜索到第idx的物体的放置状态，spV表示当前idx个物品放置状态下还有spV剩余的容量。初始调用时的参数状态为dfs_solver(1, V)，这里为了方便，物体索引从1开始，根据c/c++以及python的语言规范，下表0的相关数据为冗余空间。在这里我们以上述的输入样例来说明深度优先遍历的搜索过程。如下图所示： 上述的基于深度优先遍历的递归实现方式是物品组合方式的一种实现，效率不是很高，因为有上述的递归搜索树的实现，在程序调用上，递归函数实现过程会涉及函数及其参数的多次入栈和退栈（寄存器的一些操作，可以参考引文），这也是影响效率的主要原因（基于递归也可以有一定的优化，如有的调用参数状态会重复，这样的状态调用可以将结果暂存起来）。 而动态规划是一种基于递推的实现，计算的中间过程不断朝着目标状态演进。动态规划的实现主要是要合理的定义状态矩阵和写出状态转移方程，这里我们用二维数组dp[i][j]来描述01背包的状态，其中第一个维度的i表示已经处理到第i个物体，第二个维度的j表示容量为j时背包所装下的所有可能物体的价值总和的最大值，因此问题下的最优结果为dp[N][V](为了表示方便，下标从1开始，在c/c++和python中会引起一定的空间浪费)。基于此状态矩阵表示，这里01背包的状态方程可以写成如下的等式： dp[i][j] = max(dp[i-1][j-v[i]]+w[i], dp[i-1][j])。 也就是遍历到第i个物体总容量为j的背包所能容下物体的总价值的最大值为下面两种状态下的较大的值： 第一种：dp[i-1][j-v[i]]+w[i]，为前i-1种物体在容量为j-v[i]的状态的最大值下再放入物体i后形成的值；第二种：dp[i-1][j]为前i-1种物体在容量为j的状态的最大值下不放入第i个物体的最大值。当然也要满足容量的约束条件，而且在i为1时，j只要大于v[1], 所有的后面的d[1][>v[1]]的值均为w[1]，dp[1][<v[1]]的值均为0，这个可以认为是作为初始化条件。因此，整个动态规划的逻辑代码可以表示为如下： 后续将继续向大家介绍关于背包相关问题的解决方案。 References

树结构是数据结构中常常出现的，且用到非常多的一种数据结构。树结构中常见的有二叉树，二叉搜索树，AVL树以及B树等。树结构一般可以用递归去求解，如二叉树的遍历算法中，有先序，中序和后续遍历，一般的树结构的遍历中，有DFS（深度优先遍历）和BFS（宽度优先遍历）等都是用递归来实现。今天的实例中，有用递归直接实现的，也有用递归间接实现的。具体问题要具体分析，下面将要介绍几种具体的方法。 实例1：判断一颗二叉树是否是一个有效的二叉搜索树？ 浅析：根据二叉搜索树的递归定义，其每个节点的左子树都要比当前节点小，其右子树都要比当前节点大。一个直观的想法是：1、首先判断根节点是否满足要求，如果不满足，直接返回false，程序停止；2、再递归判断左子树是否满足要求，如果不满足，则程序返回false，依次退栈退出计算；3、再递归判断右子树是否满足要求，如果不满足，则程序返回false，依次退栈退出计算。但仔细分析发现这个思路有缺陷，不能保证右子树的最小节点比根节点要大，或者左子树的最大节点比根节点要小。这道题可以先用中序遍历（可以用递归）的方式将结果存起来，因为二叉搜索树的中序遍历结果是有序的。通过检查中序遍历结果的有序性即可判断是否为二叉搜索树。 实例2：二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。 浅析：首先判断当前节点的值，如果比low要小，说明左子树都要比low小，直接递归调用右子树即可。反之如果比high值要大，则递归调用左子树。如果在low和hight之间（假设其值为val），则，左子树上，递归调用trim[low,val]或trim[low,high],右子树上递归调用trim[low,high],或trim[val, high]。 实例3：给定二叉树的根节点root ，返回所有左叶子之和。 浅析：比较容易判断是否为叶子节点，当为叶子节点时，还需要考虑其父节点指向的左孩子是否为当前的叶子节点。递归实现的示例代码如下： 实例4：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。 浅析：通过递归可以找到要删除的节点，如果节点是叶子节点，则好办。如果不是叶子节点呢，这个时候需要找到该节点的后继节点（successor）进行替换，然后递归调用后继节点的删除操作。由于后继节点一般是右子树的最左边的节点（可能是叶子节点，可能是含有右子树的节点），删除相对比较容易，不会再次出现递归调用。这道题的具体分析可以参考引文中的说明，比较详细。 后续将继续分析更多的树类型的数据结构的不同的问题场景和解题思路。 Reference

动态规划(dynamic programming)是数据结构与算法中常用到的策略算法，一般是通过状态转移方程和初始状态来一起定义问题，从而将更大的问题转换为前面已经计算出结果的动态的更新的过程。动态规划的难点在于状态转移方程的定义，有得问题比较显而易见，而有的问题可能就比较难以定义，需要多从实际问题中总结相关的经验。 今天向大家介绍动态规划的三个示例，具体一一向大家进行介绍。 实例1：爬楼梯问题，也是经典的动态规划问题，描述如下：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 分析及解答，假设爬到n阶有methods[n]种方法，则有两种可能，先爬到n-2阶，然后跨2个台阶到达n阶，或者先爬到n-1阶，然后跨1个台阶达到n阶。因此状态转移方程为：dp[n]=dp[n-1]+dp[n-2]。初始状态为dp[0]=0,dp[1]=1,dp[2]=2。然后就可以用递推来进行循环计算了。 实例2：找零钱问题，给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。 分析及解答：假设所需最少的硬币个数为f[amount]，则状态转移方程可以表示为f[amount]=min(f[amount-conins[j]+1)，其中要求满足amount-conins[j]>0的所有的j。在递推求解的过程中，可以用双重循环来实现，外层从1到amount，内层j从0到硬币的个数-1，然后循环有个条件，及当前amount-coins[j]要大于零。 实例3：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。 分析和解答：这是和第二个问题相似但思路差别较大的问题，这里不做详细分析，直接先给出状态转移方程并作出一定的解释。状态转移方程为：problem(k,i) = problem(k-1, i) + problem(k, i-k)。其中problem(k,i) 为一个二维的状态，其中第一个维度表示用到了前面的k个硬币，i表示当前的凑的金额。problem(k-1, i)表示只用到了前面k-1个硬币就已经凑到了i，不需要第k个硬币，problem(k, i-k)表示用到了前面k个硬币凑到了i-k，已经用到了第k个硬币。 关于代码实现，后续有机会再向大家进行分享，也希望自己后面有机会向大家逐步整理关于数据结构和算法的较为系统全面的介绍，欢迎大家提出意见和建议。