目录
🌈前言
🚚动态规划介绍
🔗动态规划与递归的关系
📋动态规划的基本步骤
🌈前言
大家好，我是耀星🌟，相信大家在学习算法时会遇到很多的问题，这些问题可能你百思不得其解，有时候想着想着就放弃了，大可不必。或许能在我的指引🚩下能找到一点光明，遇到困难咱不能畏惧😱，迎刃而上一定会有所收获🏅，当然动态规划是具有一定难度🔉，题型多，没有固定模板，但是掌握解动态规划的基本过程🔃，跟着我一起学习相信你一定会对动态规划有更深入的了解。
🚚动态规划介绍
动态规划(Dynamic Programming DP)是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果--百度百科
动态规划通常用来解决最优化问题，在解决这类问题，我们通常使用一组选择来达到最优解。在做出每次选择时，通常会生成与原问题形式相同的子问题。当有N（N>1）个子问题都生成相同的子问题时，动态规划技术通常就会变的非常有效，关键技术对于每一个子问题都能保存其解，当其重复出现时即可避免重复求解。这些话看起来比较抽象，博主会通过一些简单的例子带大家入门。
🔗动态规划与递归的关系
大家在学习动态规划之前，有必要了解动态规划和递归的关系，动态规划和递归非常的相似，都是通过组合子问题的解来求解原问题，且一般递归的问题都可以转化为动态规划，咱们举个简单的例子👇斐波那契数列 。
Example 1:斐波那契数列
第i个斐波那契数列值F[i]=F[i-1]+F[i-2]，如果我们想知道F[n]，那么我们就必须要知道F[n-1]和F[n-2]的值，如果采用递归的思路，将F[n]拆分成求F[n-1]+F[n-2]，将原问题拆分成子问题求解，不同的子问题又有公共的子子问题。采用递归会做许多不必要的重复计算。例如求解F[5]:
从图中我们可以看到，F[3]和F[1]被重复计算了两次，F[2]被重复计算3次，如果要计算很多运行的效率会非常慢。我们仅仅计算F[5]就开辟了9个栈区，如果F[100]呢大概需要开辟2^99个栈区(StackOverFlow)
//递归求斐波那契数列的第N项
public static long Fac(int n)
{
if(n == 1 || n == 2)
{
return 1;
}
return Fac(n-1) + Fac(n-2);
}那么我们需要如何使用动态规划来解决这个问题呢？
对于每一个子问题都能保存其解，把每次计算出来的值用dp[i]数组保存起来。
i:表示第i个元素
dp[i]:表示第i个元素的值
public static long Fac(int n)
{
if(n <= 2)
{
return 1;
}
long dp[100] = {0};
//初始化第一个元素和第二个元素
dp[1] = 1;
dp[2] = 1;
int i = 0;
for(i = 3; i <= n; i++)
{
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}是否能够继续优化呢？
当我们计算dp[i]时，只需要知道dp[i-1]和dp[i-2]，可以利用两个局部变量来保存preFistt=dp[i-1]和preSecond=dp[i-2]的值，如果你想计算dp[i+1]，则改变preFirst=dp[i]，preSecond=dp[i-1]依次类推。
public static long Fac(int n)
{
if(n <= 2)
{
return 1;
}
//初始化
int preFirst = 1;//preFirst = dp[i-1]
int preSecond = 1;//preSecond = dp[i-2]
int ans = 0;//ans = dp[i]
int i = 0;
for(i =3; i <= n; i++)
{
ans = preFirst + preSecond;
preSecond = preFirst;
preFirst = ans;
}
return ans;
}
Example 2:走迷宫，只能向右或者向下走，小人能够到达终点的有多少种走法？
设有n行m列，想要走到(n,m)，我们只需要知道走到X=Labyrinth(n-1,m)和Y=Labyringth(n,m-1)有多少种方法，Labyrinth(n,m)=X+Y，将原问题划分为求子问题的解，就可以通过使用递归来进行计算。
public static int Labyrinth(int n, int m)
{
if(m == 1 && n == 1)
{
return 1;
}
//处理边界情况
if(m == 1 || n == 1)
{
return 1;
}
return Labyrinth(m-1, n) + Labyrinth(m, n-1);
}
使用递归同样存在着容易栈溢出的问题，那么我们如何使用动态规划来解决这个问题呢，使用一个dp[n][m]数组，将走到每一个方格的走法记录下来。
n:表示第n行
m:表示第m列
dp[n][m]:表示走到第n行第m列有多少种方法？
说明：从第0行和第0列，所有最后得到的结果储存dp[n-1][m-1]内。
public static int Labyrinth(int m, int n){
int[][] dp = new dp[n][m];
//初始化
dp[0][0] = 1;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(i == 0 || j == 0){
dp[i][j] = 1;
}
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[n-1][m-1];
}
我们还可以继续进行优化，我们可以发现我们计算dp[n-1][m-1] = dp[n-2][m-1]+dp[n-1][m-2]时只需要用到第n-1行和n-2行的元素的值，因此我们就可以用一个n=2，m=m的滚动二维数组进行计算。
public static int Labyrinth(int m, int n){
int[][] dp = new int[2][m];
//初始化
dp[0][0] = 1;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(i == 0 || j == 0){
dp[i%2][j] = 1;
continue;
}
if(i%2 == 0)//偶数行用1行的元素
dp[i%2][j] = dp[i%2][j-1] + dp[i%2+1][j];
else//奇数行用第0行的元素
dp[i%2][j] = dp[i%2][j-1] + dp[i%2-1][j];
}
}
return dp[(n+1)%2][m-1];
}
Example 3: 现在考虑网格中有障碍物，那样将会有多少条不同的路径？
网格中的障碍和空位置分别用 1 和 0 来表示。
LintCode链接：不同路径
我们用相同的思想推理：可以得到如下分段函数。
处理特殊情况：当起点和终点有障碍物时，走到终点的的方法为0。
public class Solution {
/**
* @param obstacleGrid: A list of lists of integers
* @return: An integer
*/
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// write your code here
int n = obstacleGrid.length;//获取行
int m = obstacleGrid[0].length;//获取列
if (m == 0 || n == 0) {
return 0;
}
int[][] dp = new int[n][m];
//处理特殊情况
if (obstacleGrid[0][0] == 1 || obstacleGrid[n - 1][m - 1] == 1) {
return 0;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else {
if (i == 0 && j == 0) {
dp[i][j] = 1;
} else {
if (i == 0) {
dp[i][j] = dp[i][j - 1];
} else {
if (j == 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
}
}
}
return dp[n - 1][m - 1];
}
}📋动态规划的基本步骤
1.确定状态
🚩状态在动态规划中的作用至关重要
🚩解动态规划一般要开辟一个数组，我们要明确第知道数组中每个元素dp[i]或者dp[i][j]代表什么。
🚩确定状态的两个意识
最后一步
子问题
2.列转移方程
3.初始条件和边界情况
4.计算顺序
Example 4:给定一个只含非负整数的n*m的网格，找到一条从左上角到右下角的可以使数字和最小的路径。
LintCode链接：最小路径和
1.确定状态
最优策略的路径总和数字最小
🌈若倒数第二步在(m-2, n-1)，则前面一定是从(0,0)到达(m-2,n-1)总和最小的路径
🌈若倒数第二步在(m-1, n-2)，则前面一定是从(0,0)到达(m-1, n-2)总和最小的路径
👦子问题：要求从左上角走到(m-2, n-1)和走到(m-1, n-2)的最小路径之和
👵原问题：要求走到(m-1, n-1)的最小路径之和。
⚖状态：设从(0，0)走到(i, j)的最小和路径是dp[i][j]
2.转移方程
👉说明：A[i][j]代表方格中的值
3.初始条件和边界情况
💭初始条件：
dp[i][j] = A[0][0]
🌎边界情况：
当i == 0时 dp[i][j] = dp[i][j-1] + A[i][j]
当j == 0时 dp[i][j] = dp[i-1][j] + A[i][j]
4.计算顺序
dp[0][0] dp[0][1] dp[0][2] ...dp[0][m-2] dp[0][m-1]
dp[1][0] dp[1][1] dp[1][2] ...dp[1][m-2] dp[1][m-1]
.......
dp[n-1][0] dp[n-1][1] ...dp[n-1][m-2] dp[n-1][m-1]
5.空间优化
当我们计算第i行时，只需要用到第i行和第i-1行，那么我们就可以用一个滚动数组实现，有效的节省空间。
计算第0行，处于边界情况，只需要该行就可以计算
计算第1行，只需要用到第0行
计算第2行，只需要用到第1行，删掉第0行，
计算第3行，只需要用到第2行，删掉第1行
....
public class Solution {
/**
* @param grid: a list of lists of integers
* @return: An integer, minimizes the sum of all numbers along its path
*/
public int minPathSum(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[2][m];//开辟滚动数组
int old = 0;
int now = 1;
int t1, t2;
for(int i=0; i<n; i++){
//old and now swap
now = old;
old = 1-now;
for(int j=0; j<m; j++){
if(i == 0 && j == 0){
dp[now][j] = grid[i][j];
continue;
}
dp[now][j] = grid[i][j];
if(i > 0){
t1 = dp[old][j];
}else{
t1 = Integer.MAX_VALUE;//i=0时，该行的上面元素为无穷大
}
if(j>0){
t2 = dp[now][j-1];
}else{
t2 = Integer.MAX_VALUE;//j=0时，该行的左边元素为无穷大
}
//选择较小的值到dp[now][j]
if(t1 > t2){
dp[now][j] += t2;
}else{
dp[now][j] += t1;
}
}
}
return dp[now][m-1];
}
}小结
↘求最值型动态规划
↘动态规划组成部分
-1.确定状态
🛑最后一步（最优策略中最后需要走的一步）
🛑化成子问题
-2.转移方程
🛑dp[i][j]=min{dp[i-1][j]+A[i][j],dp[i][j-1]+A[i][j]}
-3初始条件
🛑dp[0][0]=A[0][0]
-4计算顺序
dp[0][0] dp[0][1]....
空间优化
大家如果觉得有什么问题的话也可以私信我，可以和我共同讨论💬，一起学习 ！
感谢大家的支持💪！
相关文章
