题目描述: 球赛门票的售票处规定每位购票者限购一张门票,且每张门票售价50元。购票者中有m位手持50元钱币,另有n人手持100元。假设售票处开始售票时无零钱。问这m+n人有几种排队方式可使售票处不致出现找不出钱的局面。 对给定的m,n(0<=m,n<=5000),计算出排队方式总数。
示例: 输入: m = 3 n = 2 输出: 5
分析:
假设 nums[m][n]
表示,m 个 50, n 个100 ,有 nums[m][n]
个 排队总数。
- 当 m < n 时, 结果为0. 例如 3 个 50, 4 个 100, 那么怎么排列,都是不可取的。
- 当 m > n 时, 结果就是
nums[m][n] = nums[m-1][n] + nums[m][n-1]
。 - 当 m == n 时,
nums[m][n] = nums[m][n-1]
。
品一下,细细的品。
这里的 nums 我是使用的 滚动数组,品一下。这样可以解决空间,毕竟nums[m][n] 只和 nums[m-1][n] 以及 nums[m][n-1] 有关,不会和其他的 nums[m-2] 啥的有关系。 所以,我们可以设置一个两行多列的数组,滚动一下。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
nums = [ [0 for i in range(n+1)] for _ in range(2)]
for i in range(0, 2):
nums[i][0] = 1
for i in range(1, m+1):
for j in range(1, n+1):
if i-1 >= j:
nums[i%2][j] = nums[(i-1) % 2][j]
if i > j - 1:
nums[i%2][j] += nums[i%2][j-1]
# print(nums)
print(nums[m%2][n])