C#笔记：动态规划算法
- 2019 年 11 月 22 日
- 筆記
一个复杂的问题，通常逐级会分解成一系列小问题。而且很多情况下，某些小问题是相似的。但是使用传统的递归，会将相同相似的小问题进行重复的计算。这样浪费了算力。 所谓动态规划算法，实质是使用一个表，记录下所有小问题的值。如果在计算中再次遇到相同问题，则直接取值。不做计算。显然，如果每个小问题都是不同的，那么此算法没有优势。 比如斐波那契数列，就是一个简单的例子。 定义：
Fab(n)= Fab(n-1)+Fab(n-2) Fab(1)=Fab(2)=1;
实现1：
static int GetFab(int n) { if (n == 1) return 1; if (n == 2) return 1; return GetFab(n - 1) + GetFab(n - 2); }
假如我们求Fab(5) 。那我们需要求Fab（4） +Fab（3）。 Fab(4)=Fab(3)+Fab(2)…..显然。 Fab（3）被计算机不加区别的计算了两次。而且随着数字的增大，计算量是指数增长的。 如果我们使用一个数组，记录下Fab的值。当Fab(n)!=null 时。直接读取。那么，我们就能把时间复杂度控制在 n 以内。 实现2：
static int[] fab = new int[6]; static int GetFabDynamic(int n) { if (n == 1) return fab[1] = 1; if (n == 2) return fab[2] = 1; if (fab[n] != 0)//如果存在，就直接返回。 { return fab[n]; } else //如果不存在，就进入递归，并且记录下求得的值。 { return fab[n] = GetFabDynamic(n - 1) + GetFabDynamic(n - 2); } }
这就是，动态规划算法的 备忘录模式。只需要把原来的递归稍微修改就行了。 下面是0-1背包问题的解法。可以对比一下。（一个限重w的背包，有许多件物品。sizes[n]保存他们的重量。values[n]保存它们的价值。求不超重的情况下背包能装的最大价值）
static int[] size = new int[] { 3, 4, 7, 8, 9 };// 5件物品每件大小分别为3, 4, 7, 8, 9 且是不可分割的 0-1 背包问题 static int[] values = new int[] { 4, 5, 10, 11, 13 };//// 5件物品每件的价值分别为4, 5, 10, 11, 13 static int capacity = 16; static int[,] dp = new int[6, capacity + 1]; static int knapsack(int n, int w) { if (w < 0) return -10000; if (n == 0) return 0; if (dp[n, w] != 0) { return dp[n, w]; } else { return dp[n, w] = Math.Max(knapsack(n - 1, w), knapsack(n - 1, w - size[n - 1]) + values[n - 1]); /* * knapsack(n,w) 指在前N件物品在W剩余容量下的最大价值。 * 这个公式的意思是，对于某一件物品， * 1、如果选择装进去，那么，当前价值=前面的n-1件物品在空位w - size(n)下的最大价值（因为空位需要留出，空位也隐含了价值）。 * 再加上这件物品的价值。等于 knapsack(n - 1, w - size[n - 1]) + values[n - 1] * 2、 如果我们选择不装进去，那么，在n-1物品的情况下空位仍然在，当前价值 = 前面n-1件物品在空位w下的最大价值。 * 等于knapsack(n - 1, w) * 注意：随着演算，某一情况下的价值不会一成不变。 * 此时我们做出决策：到底是在装入时的价值大，还是不装入时的价值大呢？我们选择上面两种情况中值较大的。并记录在案。 * 最后dp[N,M]就是我们要求的值。 */ } }
