PDF文檔回復(fù):20241004

1 P7074 [CSP-J2020] 方格取數(shù)

[題目描述]

設(shè)有 n×m 的方格圖，每個(gè)方格中都有一個(gè)整數(shù)?，F(xiàn)有一只小熊，想從圖的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重復(fù)經(jīng)過已經(jīng)走過的方格，也不能走出邊界。小熊會(huì)取走所有經(jīng)過的方格中的整數(shù)，求它能取到的整數(shù)之和的最大值

[輸入格式]

第一行有兩個(gè)整數(shù) n,m

接下來 n行每行 m 個(gè)整數(shù)，依次代表每個(gè)方格中的整數(shù)

[輸出格式]

一個(gè)整數(shù)，表示小熊能取到的整數(shù)之和的最大值

[輸入輸出樣例]

輸入 #1

3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1

輸出 #1

9

輸入 #2

2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2

輸出 #2

-10

說明/提示

數(shù)據(jù)規(guī)模

對(duì)于 20% 的數(shù)據(jù)，n,m≤5

對(duì)于 40% 的數(shù)據(jù)，n,m≤50

對(duì)于 70% 的數(shù)據(jù)，n,m≤300

對(duì)于 100% 的數(shù)據(jù)，1≤n,m≤10^3。方格中整數(shù)的絕對(duì)值不超過 10^4

2 相關(guān)知識(shí)點(diǎn)

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃(Dynamic Programming) 是在20世紀(jì)50年代由美國數(shù)學(xué)家理查德-貝爾曼（Richard Bellman）發(fā)明的。

把原問題分解成若干子問題，自底向上求解最小子問題，把子問題的解存儲(chǔ)到表格中，然后求解較大問題，求解原問題的解時(shí)，需要用到較小子問題的解，可以直接從表格中查詢較小子問題的解，避免重復(fù)計(jì)算，從而提高求解效率

例題 斐波那契數(shù)列

如下圖

f(3)用到了3次，f(4)用到了2次，在用動(dòng)態(tài)規(guī)劃解決問題時(shí)，f(3)計(jì)算1次存儲(chǔ)表格，f(4)計(jì)算1次存儲(chǔ)表格，在使用時(shí)直接從表格取，避免重復(fù)計(jì)算，提高了速度

特別是在求較大斐波那契數(shù)時(shí)，避免了大量計(jì)算，大大提高了算法的響應(yīng)時(shí)間

動(dòng)態(tài)規(guī)劃解決問題，一般具有如下性質(zhì)

最優(yōu)子結(jié)構(gòu)

當(dāng)一個(gè)問題的最優(yōu)解包含著它的子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)

也可以認(rèn)為如果對(duì)每個(gè)子問題的最優(yōu)解可以構(gòu)建全局最優(yōu)解，說明具有最優(yōu)子結(jié)構(gòu)

斐波那契數(shù)列例子中

f(5)=f(4)+f(3) ,f(5)的解可以通過f(4)和f(3)求出，說明具有最優(yōu)子結(jié)構(gòu)

如果求問題f(5)的解和子問題f(4),f(3)等子問題的解無關(guān)，則說明不具有最優(yōu)子結(jié)構(gòu)

重疊子問題

重疊子問題是指求解問題的過程中，每次求解的問題并不是總是新問題，有大量的重復(fù)問題存在。

斐波那契數(shù)列例子中

f(3)用到了3次，f(4)用到了2次，只計(jì)算1次，存儲(chǔ)到數(shù)組中，后續(xù)使用時(shí)直接O(1)的時(shí)間復(fù)雜度直接取出

重疊子問題時(shí)動(dòng)態(tài)規(guī)劃效率高的主要原因

無后效性

把原問題分解成若干子問題，每個(gè)子問題求解都作為一個(gè)階段，求解當(dāng)前階段解時(shí)，只與之前已經(jīng)求出之前階段的解有關(guān)，和之后未求出的階段無關(guān)，這種稱作無后效性

由于之前階段問題的解已經(jīng)求出，因此無后效性是可以使用動(dòng)態(tài)規(guī)劃的前提

斐波那契數(shù)列例子中

求解f(5)與f(4)和f(3)有關(guān)，不與f(5)以后的解有關(guān)，說明其具備無后效性

關(guān)鍵連接 -動(dòng)態(tài)轉(zhuǎn)移方程

動(dòng)態(tài)規(guī)劃解決問題時(shí)，把問題分解成一個(gè)個(gè)小問題，每個(gè)問題求解時(shí)作為一個(gè)階段。當(dāng)前階段和下一個(gè)階段存在著某種聯(lián)系，這種確定的聯(lián)系，一定存在著某種方程式(根據(jù)前一階段通過某種關(guān)系式計(jì)算出下一階段)，叫做動(dòng)態(tài)轉(zhuǎn)移方程

3 思路分析

1 可以向上、向下或向右3個(gè)方向走，因此i，j位置只會(huì)依賴上，下，左3方向
2 第1列i，j位置，只會(huì)依賴上一個(gè)方向，所以第1列所有最大累加和可以先計(jì)算
3 按列逐層推進(jìn)，只需要考慮上和下2個(gè)方向
示例數(shù)據(jù)
3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1
dp[i][j]表示從1,1走到i,j的最大累加和
可以通過down和up數(shù)組取最大值獲得，max(down[i][j],up[i][j])
例如dp[1][2]=max(down[1][2],up[1][2])
具體如下圖紅色單元格

示例程序

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=1e3+10;//表格長寬最大值 
int ipt[N][N];//輸入到方格的數(shù)
/*
down[i][j] i列從長到下的累加到j(luò)最大和
up[i][j] i從下到上的累加到j(luò)最大和
dp[i][j] 從1,1開始累加到i,j的最大和
*/ 
LL down[N][N],up[N][N],dp[N][N];
int n,m;//n行 m列 int main(){scanf("%d%d",&n,&m);//輸入n行 m列 for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%lld",&ipt[i][j]);//輸入n行m列個(gè)數(shù) }}//對(duì) down,up,dp數(shù)組初始值，默認(rèn)負(fù)數(shù)最小值，小于-10^4	memset(down,128,sizeof(down));memset(up,128,sizeof(up));memset(dp,128,sizeof(dp));dp[1][1]=ipt[1][1];//dp[1][1] 為ipt[1][1] for(int i=2;i<=n;i++){//累加第1列 賦初始值 dp[i][1]=dp[i-1][1]+ipt[i][1];//第1列只能從上到下 }for(int j=2;j<=m;j++){//計(jì)算第2~m列 dp數(shù)組的值//計(jì)算j列時(shí)，j-1列已經(jīng)計(jì)算好 for(int i=1;i<=n;i++){//從上到下計(jì)算j列的最大累加和 down[i][j]=max(down[i-1][j],dp[i][j-1])+ipt[i][j];}for(int i=n;i>=1;i--){//從下到上計(jì)算j列的最大累加和 up[i][j]=max(up[i+1][j],dp[i][j-1])+ipt[i][j];}/*到i,j位置可能有3個(gè)方向(i,j-1),(i-1,j),(i+1,j) (i-1,j)對(duì)應(yīng)down[i][j], (i+1,j)對(duì)應(yīng)up[i][j]其中計(jì)算down和up時(shí)，都和 (i,j-1)做個(gè)比較取最大后+ ipt[i][j]所以down和up都大于 (i,j-1)因此值需要在down[i][j]和up[i][j]取最大即可 */ for(int i=1;i<=n;i++){ dp[i][j]=max(down[i][j],up[i][j]);}}cout<<dp[n][m];//輸出從左上角走到n,m的最大值 return 0;
}