LeetCode 2435. 矩陣中和能被 K 整除的路徑 算法：動(dòng)態(tài)規(guī)劃

設(shè) f ( i , j , t ) f(i, j, t) f(i,j,t) 表示當(dāng)前在的格子坐標(biāo)為 ( i , j ) (i, j) (i,j)，且所有到達(dá)此點(diǎn)的路徑和（包括此點(diǎn)）對(duì) k k k 取余數(shù)為 t t t 的方案數(shù)。

綠園網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)公司！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、響應(yīng)式網(wǎng)站等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)公司于2013年創(chuàng)立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)公司。

由于只能往下和往右走，因此可以得到狀態(tài)轉(zhuǎn)移方程：

f ( i , j , ( g [ i ] [ j ] + t ) % k ) = f ( i ? 1 , j , t ) + f ( i , j ? 1 , t ) f(i, j, (g[i][j] + t) \% k) = f(i - 1, j, t) + f(i, j - 1, t) f(i,j,(g[i][j]+t)%k)=f(i?1,j,t)+f(i,j?1,t)

所以只需要三重循環(huán)，前兩重枚舉坐標(biāo)，最內(nèi)層枚舉余數(shù)，從0 ~ k - 1即可

時(shí)間復(fù)雜度 O ( n m k ) O(nmk) O(nmk) C++ 代碼

typedef long long LL;

const int MOD = 1e9 + 7;

class Solution {public:
    int numberOfPaths(vector>& g, int k) {int n = g.size(), m = g[0].size();

        vector>>f(n, vector>(m, vector(k)));
        f[0][0][g[0][0] % k] = 1;

        for (int i = 0; i< n; i ++ )
            for (int j = 0; j< m; j ++ ) {if (i) {for (int t = 0; t< k; t ++ ) {auto &x = f[i][j][(g[i][j] + t) % k];
                        x = ((LL)x + f[i - 1][j][t]) % MOD;
                    }
                }
                if (j) {for (int t = 0; t< k; t ++ ) {auto &x = f[i][j][(g[i][j] + t) % k];
                        x = ((LL)x + f[i][j - 1][t]) % MOD;
                    }
                }
            }

        return f[n - 1][m - 1][0];
    }
};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章名稱：【三維DP的簡(jiǎn)單應(yīng)用】-創(chuàng)新互聯(lián)
鏈接分享：http://weahome.cn/article/deeocs.html