一文写清楚什么是动态规划
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。
1. 什么是动态规划
1.1. 百度百科对于动态规划的解释
动态规划，切勿望文生义，除非科班出身也不建议直接查看以下内容（摘抄百度百科）
-
原理编辑
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 -
概念引入
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。
-
基本思想
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
非常标准的一段话，可惜它不是人话。
1.2. 通俗的解释
How should I explain dynamic programming to a 4-year-old?
writes down “1+1+1+1+1+1+1+1 =” on a sheet of paper
“What’s that equal to?”
counting “Eight!”
writes down another “1+” on the left
“What about that?”
quickly “Nine!”
“How’d you know it was nine so fast?”
“You just added one more”
“So you didn’t need to recount because you remembered there were eight!Dynamic Programming is just a fancy way to say ‘remembering stuff to save time later’”
所以基于上述的描述，再结合百度百科中的解释
2. 动态规划相关词汇解释
2.1. 动态规划和线性规划
- 线性规划：（Linear Programming，LP）在数学中，问题是目标函数和约束条件都是线性的最优化问题。
- 动态规划：（Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
2.2. 动态规划、贪心算法、分治法、递归
-
动态规划:（Dynamic programming，DP）,动态规划算法的设计可以分为如下4个步骤：
- 描述最优解的结构；
- 递归定义最优解的值；
- 按自底向上的方式计算最优解的值；
- 由计算出的结果构造一个最优解。
-
分治法：（divide-and-conquer）将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。分治模式在每一层递归上都有三个步骤：
- 分解（Divide）：将原问题分解成一系列子问题；
- 解决（Conquer）：递归地解各个子问题。若子问题足够小，则直接求解；
- 合并（Combine）：将子问题的结果合并成原问题的解。
-
贪心算法：又称贪婪算法是使所做的选择看起来都是当前最佳的，期望通过局部最优选择来产生出一个全局最优解。
- 建立数学模型来描述问题;
- 把求解的问题分成若干个子问题；
- 对每个子问题求解，得到子问题的局部最优解；
- 把子问题的解局部最优解合成原来问题的一个解。
3. 举例说明
动态规划与其说是一个算法，不如说是一种方法论。该方法论主要致力于将合适的问题拆分成三个子目标一一击破：
- 建立状态转移方程
- 缓存并复用以往结果
- 按顺序从小往大算
完成该三个目标，你将所向披靡。
3.1 从斐波拉契数列入门动态规划
我们现在需要获取斐波拉契数列的第100位数。
- 递归实现
static void Main(string[] args)
{
{
System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
//开始监视代码
stopwatch.Start();
Console.WriteLine($"递归获取斐波拉契数列第50位数....");
Console.WriteLine(RecursionFibonacci(50));
stopwatch.Stop();
Console.WriteLine($"耗时{stopwatch.ElapsedMilliseconds / 1000}秒");
}
}
static long RecursionFibonacci(long n)
{
if (n <= 2)
{
return 1;
}
else
{
return RecursionFibonacci(n - 1) + RecursionFibonacci(n - 2);
}
}
我们发现程序随着求得斐波拉契数列得增加，程序的时间复杂度(耗时)并不是一个直线函数。可以预想再增加数值，我们需要耗费的时间。
- 动态规划实现
static long DPFibonacci(int n)
{
int[] listNums = new int[n];
for (int i = 0; i < n; i++)
{
if (i < 2)
{
listNums[i] = 1;
}
else
{
listNums[i] = listNums[i - 1] + listNums[i - 2];
}
}
return listNums[n - 1];
}
内存优化版本
static long DPFibonacciMemory(int n)
{
long num_i_1 = 0;
long num_i_2 = 0;
long TargetNum = 0;
for (int i = 0; i < n; i++)
{
if (i == 0)
{
num_i_1 = 1;
TargetNum = 1;
}
else if (i == 1)
{
num_i_2 = 1;
TargetNum = 1;
}
else
{
long temp = num_i_1 + num_i_2;
num_i_1 = num_i_2;
TargetNum = temp;
num_i_2 = TargetNum;
}
}
return TargetNum;
}
- 基于上述所总结的三步走套路我们
-
建立状态转移方程
- 通用方程都是：f(i)=f(i-1)+f(i-2)
-
缓存并复用以往结果
- 在上述中我们是将结果记录到缓存list中
-
按顺序从小往大算
- 修改计算顺序
3.2 从经典爬楼梯问题入门动态规划
有n个阶梯，一个人每一步只能跨一个台阶或是两个台阶，问这个人一共有多少种走法？
- 递归实现
private static void TheStairsProblemDemo()
{
{
System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
//开始监视代码
stopwatch.Start();
Console.WriteLine($"递归爬楼梯35级台阶....");
Console.WriteLine(RecursionTheStairsProblem(35));
stopwatch.Stop();
Console.WriteLine($"耗时{stopwatch.ElapsedMilliseconds / 1000}秒");
}
{
System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
//开始监视代码
stopwatch.Start();
Console.WriteLine($"递归爬楼梯40级台阶....");
Console.WriteLine(RecursionTheStairsProblem(40));
stopwatch.Stop();
Console.WriteLine($"耗时{stopwatch.ElapsedMilliseconds / 1000}秒");
}
{
System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
//开始监视代码
stopwatch.Start();
Console.WriteLine($"递归爬楼梯45级台阶....");
Console.WriteLine(RecursionTheStairsProblem(45));
stopwatch.Stop();
Console.WriteLine($"耗时{stopwatch.ElapsedMilliseconds / 1000}秒");
}
{
System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
//开始监视代码
stopwatch.Start();
Console.WriteLine($"递归爬楼梯50级台阶....");
Console.WriteLine(RecursionTheStairsProblem(50));
stopwatch.Stop();
Console.WriteLine($"耗时{stopwatch.ElapsedMilliseconds / 1000}秒");
}
}
public static long RecursionTheStairsProblem(int n)
{
if (n == 1)
{
return 1;
}
else if (n == 2)
{
return 2;
}
else
{
return RecursionTheStairsProblem(n - 1) + RecursionTheStairsProblem(n - 2);
}
}
- 动态规划实现
青蛙在最后一步的时候有两种跳法：
- 1）最后一步跳一级台阶，那么剩下的n-1个台阶，一共有f(n-1)种跳法
- 2）最后一步跳二级台阶，那么剩下的n-2个台阶，一共有f(n-2)种跳法
- 所以，当有n个台阶的时候，他的总可能数是上面两种情况之和
- f(n) = f(n-1)+f(n-2) 这是一种递归的关系，但是使用动态规划来解决更简单一些。
static long DPTheStairsProblem(int n)
{
long num_i_1 = 0;
long num_i_2 = 0;
long TargetNum = 0;
for (int i = 0; i <= n; i++)
{
if (i == 0)
{
num_i_1 = 0;
TargetNum = 1;
}
else if (i == 1)
{
num_i_2 = 1;
TargetNum = 1;
}
else if (i == 2)
{
num_i_1 = 1;
num_i_2 = 2;
TargetNum = 2;
}
else
{
long temp = num_i_1 + num_i_2;
num_i_1 = num_i_2;
TargetNum = temp;
num_i_2 = TargetNum;
}
}
return TargetNum;
}
3.3 中等 [LeetCode] 322. Coin Change 硬币找零
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。
-
示例 1：
输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1
- 递归实现
public static void CoinChange()
{
{
System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
stopwatch.Start();
Console.WriteLine($"递归硬币问题....");
int[] CoinArr = new int[] { 2, 5, 7 };
Console.WriteLine(FuncRecursionCoinChange(CoinArr, 27));
stopwatch.Stop();
Console.WriteLine($"耗时{stopwatch.ElapsedMilliseconds / 1000}秒");
}
{
System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
stopwatch.Start();
Console.WriteLine($"递归硬币问题....");
int[] CoinArr = new int[] { 2, 5, 7, 3, 4 };
Console.WriteLine(FuncRecursionCoinChange(CoinArr, 45));
stopwatch.Stop();
Console.WriteLine($"耗时{stopwatch.ElapsedMilliseconds / 1000}秒");
}
{
System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
stopwatch.Start();
Console.WriteLine($"递归硬币问题....");
int[] CoinArr = new int[] { 2, 5, 7, 3, 4 };
Console.WriteLine(FuncRecursionCoinChange(CoinArr, 52));
stopwatch.Stop();
Console.WriteLine($"耗时{stopwatch.ElapsedMilliseconds / 1000}秒");
}
}
static int FuncRecursionCoinChange(int[] A,int X)
{
if (X == 0)
{
return 0;
}
int res = 1000;
foreach (var item in A)
{
if (X >= item)
{
res = Math.Min(FuncRecursionCoinChange(A,X - item) + 1, res);
}
}
return res;
}
- 动态规划实现
static long DPCoinChange(int[] A, int M)
{
int[] f = new int[M + 1];
f[0] = 0;
int i,j;
for (i = 1; i <= M; i++)
{
f[i] = Int32.MaxValue;
for (j = 0; j < A.Length; j++)
{
if (i >= A[j] && f[i - A[j]] != Int32.MaxValue)
{
f[i] = Math.Min(f[i-A[j]]+1,f[i]);
}
}
}
return f[M];
}
- 动态规划细节问题
-
动态规划转移方程：
- f(X)=min{f(x-2)+1,f(x-5)+1,f(x-7)+1}
3.4 机器人问题
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
- 动态规划分析
- 动态规划实现
public int UniquePaths(int m, int n) {
int[,] f=new int[m,n];
int i,j;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
if (i == 0 || j == 0)
{
f[i,j]=1;
}
else
{
f[i,j]=f[i-1,j]+f[i,j-1];
}
}
}
return f[m-1,n-1];
}
3.5 存在性动态规划 JumpGame
跳跃游戏 leetcode 55题
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
-
示例 1：
输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 -
示例 2：
输入：nums = [3,2,1,0,4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
- 动态规划代码实现
public bool CanJump(int[] A)
{
int n=A.Length;
bool[] f=new bool[n];
f[0]=true;
for (int i = 1; i < n; i++)
{
f[i]=false;
for (int j = 0; j < i; j++)
{
if(f[j]&&j+A[j]>=i)
{
f[i]=true;
break;
}
}
}
return f[n-1];
}
总结
动态规划题目特点
-
计数
- 有多少种方式走到右下角
- 有多少种方法选出k个数使得和是sum
-
求最大值和最小值
- 从左上角到右下角路径的最小步数
- 最长上升子序列长度
-
求存在性
- 取石子游戏，先手是否必胜
- 能不能选出k个数使得和为sum
常见动态规划类型
- 坐标型动态规划
- 序列型动态规划
- 划分型动态规划
- 区间型动态规划
- 背包型动态规划
- 最长序列型动态规划
- 博弈型动态规划
- 综合型动态规划
- 动态规划打印路径
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
19
0- 0
已为社区贡献12条内容
所有评论(0)