动态规划入门

• Z时代
• 2024-01-10
• 分类：技术分享

首先用最经典的一道题来引入动态规划" title="动态规划">动态规划

动态规划（dynamic programming）

请看下面这个题

一个十分漂亮的数字三角形；求哪条路径能使得各个数字的和最大；

如果我们只是单纯的贪心，即每次选择最大值走，

那么结果就是7+8+1+7+5=28；

但是，7+3+8+7+5这条路径等于三十30；

显然，不能使用贪心的思想；

这时候，就需要使用动态规划的思想；

主要思想：

将问题可以看为多个相同的小问题，寻找最优子结构，利用局部最优解推导出整体最优解；

这个类似于完全二叉树的东西，每一个父节点都有两个子节点，那么父节点的路径只有他的两个子结构，所以此时我们需要找出哪一个子节点大，

例如：

2

4 5

这个节点；

显然5>4，那么我们递推的时候就会采用5而不是4；

假设第i行j列的节点为dp[i][j]；

那么他的递推公式就是dp[i][j]+=max{dp[i-1][j],dp[i-1][j];

选择大的字节；一层一层累加上去，那么dp[0][0]便是最大路径的值

源码如下：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
usingnamespace std;
int num[1001][1001];
intmain()
{
int n;
cin >> n;
for(int i =0; i < n; i++)
{
for(int j =0; j <= i; j++)
{
cin >> num[i][j];
}
}
for(int i = n-1; i >=0; i--)
{
for(int j =0; j <= i; j++)
{
num[i][j]=(num[i +1][j]> num[i +1][j +1]? num[i +1][j]: num[i +1][j +1])+ num[i][j];
}
}
cout << num[0][0];
return0;
}

所以说，动态规划大致就分为以下步骤：

1. 拆分问题；
2. 找递推公式（状态转移方程）；
3. 确定边界；

   再看一道：

   

leetcode 70；

问题问，有几种方法；题目已知，可以跳一个，也可以跳两个，假设跳到第i个的时候，绝对是从第i-1或者i-2个楼梯来的，那么他的状态转移方程就出来了

dp[i]=dp[i-1]+dp[i-2]；

然后确定边界，首先第0个绝对是0种方法，第1个也只有一种，第二个有2种，；

即dp[1]=1,dp[2]=2；

源码如下：

intclimbStairs(int n)
{
int dp[50]={1,2};
for(int i=2;i<n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n-1];
}

最后，再来一道leetcode与上题相近的中等题

这个时候，我们根据上个题，可以很容易想来；

第i行j列的方法，就是第i-1行j列+第i行j-1列之和；

所以他的递推公式就是:dp[i][j]=dp[i-1][j]+dp[i][j-1];

此时地图的最上一行和最左边的一行；他们都只能由一种走来；

最上面的一行每一个格子只能由他的左边走来，最左边的格子只能由他上面的格子走来；

所以，这个题的初始化就是：

int dp[m][n];
for(int i=0;i<m;i++)
{
dp[i][0]=1;
}
for(int i=0;i<n;i++)
{
dp[0][i]=1;
}

现在知道状态转移方程和边界；

直接上源码：

intuniquePaths(int m,int n){
int dp[m][n];
for(int i=0;i<m;i++)
{
dp[i][0]=1;
}
for(int i=0;i<n;i++)
{
dp[0][i]=1;
}
for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}

以上是 动态规划入门 的全部内容， 来源链接： utcz.com/a/118103.html