牛客網之Shopee的辦公室

• 題目連結
• 題目原型：不同路徑2
• 分析：這道題的部落客記錄下來的原因在于，資料看起來較小，但是結果用int型會溢出，進而導緻結果錯誤。
• 狀态轉移方程：

//當然這些如果在老闆處，方程需要作出修改；
dp[i][j]=dp[i-1][j]+dp[i][j-1];
           

• 初始化：

for(i=0;i<=x;i++) dp[i][0]=1;
for(j=0;j<=y;j++) dp[0][j]=1;
           

• 核心代碼：

long long fun(int &x,int &y,vector<vector<int>> &arr
		vector<vector<long long>> &dp){
    for(int i=1;i<=x;i++){
        for(j=1;j<=y;j++){
            dp[i][j]=0;
            if(arr[i][j]==1){
                if(arr[i][j-1]==1) dp[i][j]+=dp[i][j-1];
                if(arr[i-1][j]==1) dp[i][j]+=dp[i-1][j];
            }
        }
    }
}