目錄
動態(tài)規(guī)劃的初步理解
求最短路徑數(shù)
洛谷 P1002 過河卒?
題目描述
輸入樣例
輸出樣例?
思路
AC Code
Everyday English
The greatest glory in living lies not in never falling, but in rising every time we fall.
生命中最大的榮耀不在于從未跌倒，而在于每次跌倒后都能重新站起來。
動態(tài)規(guī)劃的初步理解
什么是動態(tài)規(guī)劃？最直白的理解就是動態(tài)的規(guī)劃。
那高級一點的理解呢？就是每時每刻都拿著一個小本本，也就是記事本，把干的事情都記錄下來，不斷規(guī)劃自己的策略，這就是動態(tài)規(guī)劃。
動態(tài)規(guī)劃里的小本本就對應(yīng)著程序里的數(shù)組，而策略不就是往里依次填值嗎。
動態(tài)規(guī)劃理解到這，恭喜你，你已經(jīng)了解了動態(tài)規(guī)劃了。簡單吧！
那我們邊講題，邊理解！
動態(tài)規(guī)劃我們一般用dp來表示。
求最短路徑數(shù)
問從A（1,1）走到B（n,m）有幾種最短路徑（每次只能向相鄰的格子走一格）？
要求：輸入B的行坐標(biāo)(n)和列坐標(biāo)(m)，輸出最短路徑總數(shù)
這題咋一看，毫無頭緒，是嵌套for循環(huán)？還是while？都不是，是DP，你看：
假設(shè)輸入的是2和3，那么先把格子畫出來，是這樣的。
那每個格子里該填什么呢？對了，應(yīng)該填到當(dāng)前格子的最短路徑數(shù)。那是不是每個格子都要從頭輸一遍呢？你仔細想想，題目說要最短，那走回頭路肯定不行，那只能往下走或者右走，這樣才能確保最短。因此每一格的最短路徑數(shù)，不就是它上面的格子+左邊的格子嗎？
知道了DP公式，那好做了。
填完就是這樣的，你可以驗證一下：
最后輸出dp[n][m]就完事了，上代碼：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,dp[505][505];
memset(dp,0,sizeof(dp));
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i==1&&j==1) dp[i][j]=1;//第一個格子只有一條路徑
else
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
cout<<dp[n][m]<<endl;
return 0;
}洛谷 P1002 過河卒?
網(wǎng)址：[NOIP2002 普及組] 過河卒 - 洛谷
題目描述
棋盤上?A?點有一個過河卒，需要走到目標(biāo)?B?點。卒行走的規(guī)則：可以向下、或者向右。同時在棋盤上?C?點有一個對方的馬，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。因此稱之為“馬攔過河卒”。
棋盤用坐標(biāo)表示，A?點?(0,0)、B?點?(n,m)，同樣馬的位置坐標(biāo)是需要給出的。
現(xiàn)在要求你計算出卒從?A?點能夠到達?B?點的路徑的條數(shù)，假設(shè)馬的位置是固定不動的，并不是卒走一步馬走一步。
輸入樣例
6 6 3 3輸出樣例?
6思路
這題看上去不就是DFS嗎，簡簡單單直接提交，可是……?
成功的超了時，那咋辦，對了之前我不是講過DP嗎，沒看的回我主頁看看。這題數(shù)據(jù)較大，用DP不快嗎？
那DP公式是啥呢？這里需要用到象棋知識，當(dāng)卒過河后是不能向后走的，那么DP數(shù)組的每一格就是他上一格的路徑數(shù)+左邊一格的路徑數(shù)（這個和我講的DP特別像，不理解的去看我的DP文章）。當(dāng)然馬能攔住的地方開始都得給他設(shè)成不能走。文章來源：http://www.zghlxwxcb.cn/news/detail-827119.html
那代碼不就So Easy了嗎，上代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-827119.html
AC Code
#include<iostream>
#include<algorithm>
using namespace std;
long long dp[30][30];
int dx[8]={-2,-2,-1,-1,1,1,2,2},dy[8]={1,-1,2,-2,2,-2,1,-1};//馬跳的坐標(biāo)變化
int main(){
int n,m,x,y;
cin>>n>>m>>x>>y;
n+=1;m+=1;x+=1;y+=1;
for(int i=0;i<8;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m)
dp[nx][ny]=-1;
}
dp[1][0]=1;
dp[x][y]=-1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dp[i][j]==-1)
dp[i][j]=0;
else{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
cout<<dp[n][m];
return 0;
}
到了這里，關(guān)于秒懂百科，C++如此簡單丨第十九天：動態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
