Tere是大小为R×C的表格； R行和C列。
表格的子矩形被阻止。
我们只能向右或向下移动。从左上单元格到右下单元格但未通过被阻止的子矩形的路径数是多少？
我的方法:
计算从行r2 C = {0到c1-1}的路径和从行r1 C = {c2 + 1，C}的路径
r1，c1，r2和c2，即所矩形的左上角单元和右下角单元。
Cal Calculate C(n,k)
我的代码:
int R = in.nextInt()-1;
int C = in.nextInt()-1;
int r1 = in.nextInt()-1;
int c1= in.nextInt()-1;
int r2 = in.nextInt()-1;
int c2 = in.nextInt()-1;
long ans=0;
long temp=0;
temp+= Cal(R-r2+C-c1,C-c1);
for(int i=0;i<c1 && r2!=R;i++){
ans+=Cal(i+r2,r2)*(Cal(R-r2+C-i,C-i)-temp);
}
temp=0;
temp+=Cal(r1+c2,r1);
for(int i=c2+1;i<=C;i++){
ans+= (Cal(i+r1,r1)-temp)*Cal(C-i+R-r1,C-i);
}
System.out.println(ans);
对于上述算法，我没有得到正确的答案。如果我做错了，请帮助我。
Sample input:
8 12
5 5 8 8 ANS:7008
最佳答案
我建议使用动态编程方法来解决此问题。面板中的每个“畅通无阻”单元都有一个与之关联的数字，即到达右下角的方式的数量；目前，该数字在每个单元格中均未定义。
最好用一个例子对此进行解释。假设我们有
O
OXXOOO
OXXOOO
O
O
作为我们的板，X表示障碍物，O是一个正方形，我们尚未填充到右下角的路径数。现在，我们从右下角向后工作。我们将首先填写右下角的数字1，尽管这可能没有什么意义。
O
OXXOOO
OXXOOO
O
OOOOO1
现在可以填充最靠近右下角的两个正方形。它们很简单。
O
OXXOOO
OXXOOO
OOOOO1
OOOO11
现在我们可以再填充3个正方形:
O
OXXOOO
OXXOO1
OOOO21
OOO111
在每种情况下，我们所做的只是将一个正方形右侧的数字和一个正方形下方的数字相加，我们想象零在板的右侧和底部。下一步:
O
OXXOO1
OXXO31
OOO321
OO1111
到目前为止，我们正在获得二项式系数，这是我们在类似问题中所期望的。下一步:
OOOOO1
OXXO41
OXX631
OO4321
O11111
更多二项式系数。下一步:
OOOO51
OXXA41
OXX631
O54321
111111
我使用字母A表示10。这就像二项式系数，但是我们缺少一些现有的东西。但是，很快就会改变。下一步:
OOOF51
OXXA41
OXX631
654321
111111
注意使用F表示15。现在事情变得有趣了。由于我们无法穿过障碍物，因此将0与障碍物中的像元相关联。要填充右上角的空白，我们添加F + 0 =F。类似地，0 + 6 = 6。
OOFF51
OXXA41
6XX631
654321
111111
下一步:
OFFF51
6XXA41
6XX631
654321
111111
最后一步:
UFFF51
6XXA41
6XX631
654321
111111
在这里，我使用U表示21 = F +6。这就是问题的答案。
该程序通常可以正常工作。我们可以填写任何我们知道右侧和下方数字的单元格，然后逐步填充整个矩形。