以下の動的計画法を行います。

\(dp[i][j][k] = {}\)( 区画 \((i, j)\) までに \(k\) 匹魚を釣るときのおいしさの合計の最大値 )

漸化式は以下のようになります。

\[ \begin{aligned} dp[i][j][k] = \max(&dp[i-1][j][k],\\ &dp[i][j-1][k],\\ &dp[i-1][j][k-1] + A_{i,j},\\ &dp[i][j-1][k-1] + A_{i,j}) \end{aligned} \]

状態数が \(O(HW(H+W))\) 、遷移が \(O(1)\) なので、時間計算量は \(O(HW(H+W))\) です。

回答例 (C++)

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
void chmax(ll& a, ll b){ if(a < b) a = b; }

int main(){
    ll H, W;
    cin >> H >> W;
    vector A(H, vector<ll>(W));
    for(auto& a : A) for(ll& i : a) cin >> i;
    const ll K = H + W - 1;
    vector dp(H, vector(W, vector<ll>(K + 1)));
    for(ll i = 0; i < H; i++){
        for(ll j = 0; j < W; j++){
            if(i) for(ll k = 0; k <= K; k++) chmax(dp[i][j][k], dp[i - 1][j][k]);
            if(j) for(ll k = 0; k <= K; k++) chmax(dp[i][j][k], dp[i][j - 1][k]);
            for(ll k = K; k--; ) chmax(dp[i][j][k + 1], dp[i][j][k] + A[i][j]);
        }
    }
    for(ll k = 1; k <= K; k++) cout << dp.back().back()[k] << ' ';
}

回答例 (Python)

H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
K = H + W - 1
dp = [[[]] * W] * H
for i in range(H):
    for j in range(W):
        if i and j:
            a = [max(x, y) for x, y in zip(dp[i - 1][j], dp[i][j - 1])]
        elif i:
            a = dp[i - 1][j][:]
        elif j:
            a = dp[i][j - 1][:]
        else:
            a = [0] * (K + 1)
        x = A[i][j]
        for k in reversed(range(K)):
            if a[k + 1] < a[k] + x:
                a[k + 1] = a[k] + x
        dp[i][j] = a
print(*dp[-1][-1][1:])