做政协网站软件的公司,宁夏网站建设联系电话,福田网站的建设,wordpress 邮箱 通知文章目录 dp是什么如何发现一个题符合dpdp题目dp是什么
dp也就是动态规划算法，空间换时间的思想。 通过利用储存的子问题信息高效求出当前问题的最优解。
如何发现一个题符合dp
1.能够通过一个子问题推到另一个最优子结构，利用计算出的信息得到最优解。 2.遵循一个顺序，重… 文章目录 dp是什么如何发现一个题符合dpdp题目 dp是什么
dp也就是动态规划算法，空间换时间的思想。 通过利用储存的子问题信息高效求出当前问题的最优解。
如何发现一个题符合dp
1.能够通过一个子问题推到另一个最优子结构，利用计算出的信息得到最优解。 2.遵循一个顺序，重复计算子问题，且无后效性。 其中具有最优子结构也可能是适合用贪心的方法求解。 无后效性的意思就是后面的情况影响不到前面。
dp题目
P1216 数字三角形 题意：找到一条路的权值和最大 思路：因为这条路有一个特点，从a[i][j]到a[i+1][j]或a[i+1][j+1]，所以很容易想到式子为dp[i][j]=dp[i-1][j]+dp[i-1][j-1]，又因为要最大，所以就可以求一个max，来求出最优子结构，因为是从上往下走，且a[i][j]都大于等于0，所以最后再到最后一行去找最大值。
#include bits/stdc++.h
using namespace std;
#define ll long long
const int maxx=1010;
ll dp[maxx][maxx];
ll b[maxx][maxx];
int main()
{int n;scanf("%d",n);for(int i=1;i=n;i++){for(int j=1;j=i;j++){scanf("%lld",b[i][j]);}}for(int i=1;i=n;i++){for(int j=1;j=i;j++){dp[i][j]=max(dp[i-1][j]+b[i][j],dp[i][j]);dp[i][j]=max(dp[i-1][j-1]+b[i][j],dp[i][j]);}}ll ans=0;for(int i=1;i=n;i++){ans=max(ans,dp[n][i]);}printf("%lld\n",ans);} P1434 滑雪 题意：给一个二维数组，每个数代表一个高度，选择一个点走，可以上下左右走，但只能从高到低，求最长的路。 思路：最容易想到搜索，但怎么用dp去写。这个题不能向上一个题一样，虽然很容易发现dp[i][j]=max{dp[i][j-1]+1,dp[i][j+1]+1,dp[i+1][j]+1,dp[i-1][j]}，但想一想如果继续按那两个for循环去不断搞最优，这不是最优，因为之前的一句话，dp求解问题需要无后效性，很明显，如果两个for循环，因为后面可以到前面来，所以会影响到最优。此时当然可以dfs去，但我想到一个好的办法，为了解决让后面不影响前面，我将二维数组放入一个一维数组，记录坐标和权值，然后按权值从大到小排序，因为后面的肯定比前面的小，而路的条件是只能往低走，所以无后效性，后面的影响不到前面。因此可以得到最优解。
#include bits/stdc++.h
using namespace std;
#define ll long long
const int maxx=1010;
int dp[maxx][maxx];
int b[maxx][maxx];
struct point
{int x;int y;int w; } a[maxx*maxx];bool cmp(point x,point y){return x.wy.w;}
int main()
{int n,m;scanf("%d%d",n,m);int cnt=0;for(int i=1;i=n;i++){for(int j=1;j=m;j++){scanf("%d",b[i][j]);a[++cnt].x=i;a[cnt].y=j;a[cnt].w=b[i][j];}}sort(a+1,a+cnt+1,cmp);int ans=0;for(int i
