TIOJ-1268
DP題
紀錄每個位置的能得到最大分數
可以選擇向右、向下、不走，所以
\[ f(x, y) = max(f(x+1, y), f(x, y+1), 0) \]
一開始一直 WA ，後來發現 ans 忘記初始設 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<bits/stdc++.h>
int c[3005][3005], m[3005][3005];
int M, N;
int dp(int x, int y){
if(x>=M||y>=N) return 0;
if(c[x][y]) return c[x][y];
return c[x][y] = std::max(std::max(dp(x+1, y)+m[x+1][y], dp(x, y+1)+m[x][y+1]), 0);
}
int main(){
int ans=0, tmp;
scanf("%d%d", &M, &N);
memset(m, 0, sizeof(m));
for(int i=0; i<M; i++){
for(int j=0; j<N; j++){
scanf("%d", &m[i][j]);
}
}
for(int i=0; i<M; i++){
for(int j=0; j<N; j++){
tmp = m[i][j]+dp(i, j);
if(tmp>ans) ans = tmp;
}
}
printf("%d", ans);
}
|