動態規劃的引入
之前學習過一段時間的動態規劃，但掌握的不夠牢固，實際做題時還是不能靈活的運用，所以打算在寒假對這部分知識進行學習和鞏固，按照洛谷的提單分為五個部分進行學習：
1.動態規劃的引入
2.線性狀態動態規劃
3.區間與環形動態規劃
4.樹與圖上的動態規劃
5.狀態壓縮動態規劃
本文題目選自第一部分的練習內容
題目：過河卒
題目內容：棋盤上 AA 點有一個過河卒，需要走到目標 BB 點，卒行走的規則：可以向下、或者向右，同時在棋盤上 CC 點有一個對方的馬，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點，因此稱之為“馬攔過河卒”，棋盤用坐標表示，AA 點 (0, 0)(0,0)、BB 點 (n, m)(n,m)，同樣馬的位置坐標是需要給出的，現在要求你計算出卒從 AA 點能夠到達 BB 點的路徑的條數，假設馬的位置是固定不動的，并不是卒走一步馬走一步，
樣例： 輸入：6 6 3 3 輸出： 6
解題程序：這道題很明顯要用動態規劃的思想來做，直接算出有多少條路是不現實的，所以拆分成算每一格有多少條路，并把馬的控制點做為動態規劃的條件：
1.當上一步和左一步都是馬的控制點時，到這一步的路數為： 0+0 = 0
2.當僅有上一步是馬的控制點時，到這一步的路數為： 0 + 左一步的路數 = 左一步的路數
3.當僅有左一步是馬的控制點時，到這一步的路數為： 上一步的路數 + 0 = 上一步的路數
3.當上一步和左一步都不是馬的控制點時，到這一步的路數為： 上一步的路數+左一步的路數
代碼為：
if(area[i-1][j]==-1 && area[i][j-1]==-1) area[i][j] = 0;
else if(area[i-1][j]==-1) area[i][j] = area[i][j-1];
else if(area[i][j-1]==-1) area[i][j] = area[i-1][j];
else area[i][j] = area[i][j-1] + area[i-1][j];
注意判斷邊界，即馬的控制點會不會超出棋盤范圍：
if(hx-2 >= 0 && hy-1 >=0)
area[hx-2][hy-1] = -1;
if(hx-1 >= 0 && hy-2 >=0)
area[hx-1][hy-2] = -1;
if(hx+1 <= bx && hy-2 <= by)
area[hx+1][hy-2] = -1;
if(hx+2 <= bx && hy-1 >=0)
area[hx+2][hy-1] = -1;
最后還要注意路數會超出int范圍，所以dp陣列要用long long int存盤（因為這個細節第一次提交WA的兩個樣例）：
long long int area[25][25];
全部代碼：
#include<bits/stdc++.h>
using namespace std;
long long int area[25][25];
int bx,by,hx,hy;
void init(){
for(int i=0;i<=by;i++){
if(area[0][i] != -1) area[0][i] = 1;
else break;
}
for(int j=0;j<=bx;j++){
if(area[j][0] != -1) area[j][0] = 1;
else break;
}
}
void dp(){
for(int i=1;i<= bx;i++){
for(int j=1;j<=by;j++){
if(area[i][j] == -1) continue;
if(area[i-1][j]==-1 && area[i][j-1]==-1) area[i][j] = 0;
else if(area[i-1][j]==-1) area[i][j] = area[i][j-1];
else if(area[i][j-1]==-1) area[i][j] = area[i-1][j];
else area[i][j] = area[i][j-1] + area[i-1][j];
}
}
}
int main(){
cin >> bx >> by >> hx >> hy;
area[hx][hy] = -1;
if(hx-2 >= 0 && hy-1 >=0)
area[hx-2][hy-1] = -1;
if(hx-1 >= 0 && hy-2 >=0)
area[hx-1][hy-2] = -1;
if(hx+1 <= bx && hy-2 <= by)
area[hx+1][hy-2] = -1;
if(hx+2 <= bx && hy-1 >=0)
area[hx+2][hy-1] = -1;
if(hx-2 >= 0 && hy+1 <= by)
area[hx-2][hy+1] = -1;
if(hx-1 >= 0 && hy+2 <= by)
area[hx-1][hy+2] = -1;
if(hx+1 <= bx && hy+2 <= by)
area[hx+1][hy+2] = -1;
if(hx+2 <= bx && hy+1 <= by)
area[hx+2][hy+1] = -1;
init();
dp();
cout << area[bx][by];
}
心得：
通過今天的練習，我復習了之前練習的動態規劃的題目，學習了動態規劃的思想，即把一個無法直接得到答案的復雜問題分成若干個較簡單的小問題，通過對小問題進行求解并匯總最終得到大問題的答案，這一思想不僅在編程中很厲害，在現實生活中對我也有所啟發，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/244756.html
標籤：其他
上一篇：無刷直流電動機矢量控制（四）——simulink仿真搭建（讓電機動起來）
下一篇：一鍵錄屏神器——Captura