資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中計算所有有效的取貨和送貨選項
假設我們有n個訂單的列表，每個訂單都有取貨和送貨服務。我們必須計算所有有效的取貨/送貨可能序列，使得delivery[i]總是在pickup[i]之後。由於答案可能非常大，我們將返回它對10^9 + 7取模的結果。
因此，如果輸入為2，則輸出為6，因為所有可能的訂單為(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) 和 (P2,D2,P1,D1)。而訂單(P1,D2,P2,D1)無效，因為取貨2在送貨2之後。
為了解決這個問題，我們將遵循以下步驟：
m := 10^9 + 7
N := 550
定義一個大小為(N+5) x (N+5)的陣列dp。用-1填充它。
定義一個函式add()，它將接收a, b，
返回((a mod m) + (b mod m)) mod m
定義一個函式mul()，它將接收a, b，
返回((a mod m) * (b mod m)) mod m
定義一個函式solve()，它將接收inPickup, left, i, j，
如果i等於0且j等於0，則：
返回1
如果dp[i, j]不等於-1，則：
返回dp[i, j]
ret := 0
如果i > 0，則：
ret := add(ret, mul(left, solve(inPickup + 1, left - 1, i - 1, j)))
如果j > i，則
ret := add(ret, mul(inPickup, solve(inPickup - 1, left, i, j - 1)))
返回dp[i, j] = ret
從主方法執行以下操作：
返回solve(0, n, n, n)
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
const int N = 550;
int dp[N + 5][N + 5];
lli add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
lli mul(lli a, lli b){
return ((a % m) * (b % m)) % m;
}
class Solution {
public:
void pre(){
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dp[i][j] = -1;
}
}
}
int solve(int inPickup, int left, int i, int j){
if (i == 0 && j == 0)
return 1;
if (dp[i][j] != -1)
return dp[i][j];
int ret = 0;
if (i > 0) {
ret = add(ret, mul(left, solve(inPickup + 1, left - 1, i
- 1, j)));
}
if (j > i) {
ret = add(ret, mul(inPickup, solve(inPickup - 1, left, i,
j - 1)));
}
return dp[i][j] = ret;
}
int countOrders(int n){
pre();
return solve(0, n, n, n);
}
};
main(){
Solution ob;
cout << (ob.countOrders(2));
}輸入
2
輸出
6
更新於：2020年6月8日
170 次瀏覽
廣告