C++ 使用递归、回溯、动态规划算法实现一题多解

１. 引言

为了让大家更好理解递归、回溯、动态规划三者算法之间有关系，本文罗列了几道题目，分别使用递归、回溯、动态规划解决。会发现三者之间同工异曲，都是一种搜索模式，递归是正向搜索且返回；回溯是搜索到尽头后你自己看着办、然后再继续；动态规划可以理解为反向搜索。

要有一定深度的理解，需要自己反复练习且揣摩其中的细节之分。

本文直接提出问题，直接给出答案。

2. 打家劫舍

2.1 问题描述

一个专业的盗贼，计划偷打劫街的房屋。每间房内都藏有一定的现金，你可以进入每一间房子，影响偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被盗贼闯入，系统会自动报警。

现给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例1：输入：[1,2,3,1]

输出：4

解释：偷窃 1号房屋(金额=1)，然后偷窃3号房屋(金额=3)。偷窃到的最高金额=1+3=4。

示例2：

输出：12

解释：偷窃 1 号房屋(金额 = 2)，偷 3 号房屋(金 = 9)，接着偷 5 号房屋(金额 =1)偷窃到的最高金额=2+9+1=12。

2.2 递归实现

2.2 回溯实现

2.3 动态规划

3. 找零钱

3.1 问题描述

给你种面值的硬币，面值分别为，每种硬币的数量无限，再给一个总金额，问最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 。

比如说，面值分别为 ，总金额。那么最少需要 枚硬币凑出，即 。

3.2 递归实现

3.3  回溯实现

3.4 动态规划实现

4. 背包

4.1 问题描述

有一个可装载重量为的背包和个物品，每个物品有重量和价值两个属性。其中第个物品的重量为，价值为，现在用这个背包装物品，最多能装的价值是多少？

题目中的物品不可以分割，要么装进包里，要么不装，不能切成两块装一半。

可以选择前两件物品装进背包，总重量 小于，可以获得最大的价值是 。

4.2 递归实现

4.3 回溯实现

4.4 动态规划实现

5. 小结

只看不练假把式，只练不思假学问。