算法题 - 贷款违约K笔的概率 - Python
问题描述：
有N笔贷款，每笔贷款违约的概率为 [p1、p2、p3 ... ... pn]，求恰好有K笔贷款违约的概率。
前提条件:（我自己加的哈）
- 每笔贷款违约的概率相互独立，且概率值
p在[0, 1]范围内。
问题分析：
这是今天头条的第二个面试题，自己想到动态规划来做了，但是，被这个概率计算给搞懵逼了，想的特别复杂，感觉好菜，事实说明数学才是其他学科的基础呀。自己写对了一半，在面试官的提示下，才写对递推方程式，惭愧。
现在直接给出递推方程式，然后再去解读：
表示，有n笔贷款时，恰好有k次违约的概率，这个值怎么求那？可以从子问题入手，要想得到这个值，不难发现有两个方向：
（1）dp[k][n-1]表示有n-1笔贷款时，恰好有k次违约的概率，现在已经恰好k次了，那么新来的那个贷款 没有违约就可以继续保持k次了，所以是：
（2）dp[k-1][n-1]表示有n-1笔贷款时，恰好有k-1次违约的概率，现在是恰好k-1次，那么新来的那个贷款 违约了，不就是k次了吗，所以是：
所以综上所述，就可以得出上面的递推式了：
需要注意的地方是： 边界的处理，也就是k=0 或 n=0的情况，要单独计算。现在看一个例子：
输入数据为： N, K, P = 4, 3, [0.8, 0.9, 0.7, 0.6]
可以得出dp:
Python3实现：
现在的时间复杂度为O(kn), 空间复杂度为O(kn)
# @Time :2019/02/12
# @Author :LiuYinxing
# Python3
# 动态规划
class Solution:
def probabilityK(self, N, P, K):
if N <= 0 or N < K: return 0
dp = [[-1] * (N + 1) for _ in range(K + 1)] # 开辟dp
# 初始化 dp 边界
dp[0][0] = 1
for n in range(1, N+1): # 上边界
dp[0][n] = dp[0][n-1] * (1 - P[n-1])
for k in range(1, K+1): # 左边界
dp[k][0] = 0
for k in range(1, K+1): # 计算dp
for n in range(1, N+1):
dp[k][n] = dp[k][n-1] * (1 - P[n-1]) + dp[k-1][n-1] * P[n-1]
return dp[-1][-1] # 返回结果
if __name__ == '__main__':
solu = Solution()
N, K = 4, 3
P = [0.8, 0.9, 0.7, 0.6]
print(solu.probabilityK(N, P, K))
压缩dp空间（可以结合上图理解）现在的时间复杂度为O(kn), 空间复杂度为O(n)
# @Time :2019/02/12
# @Author :LiuYinxing
# Python3
# 动态规划，压缩dp空间
class Solution:
def probabilityK(self, N, P, K):
if N <= 0 or N < K: return 0
dp = [-1] * (N + 1) # 开辟dp
# 初始化 dp 边界
dp[0] = 1
for n in range(1, N+1): # 上边界（第一行）
dp[n] = dp[n-1] * (1 - P[n-1])
for k in range(1, K+1): # 计算dp
pre = 0 # 表示 要计算当前值的前一个值
for n in range(1, N+1):
temp = pre * (1 - P[n-1]) + dp[n-1] * P[n-1]
dp[n-1], pre = pre, temp
dp[N] = pre
return dp[-1] # 返回结果
if __name__ == '__main__':
solu = Solution()
N, K = 4, 3
P = [0.8, 0.9, 0.7, 0.6]
print(solu.probabilityK(N, P, K))
同理，也可以把空间复杂度压缩为O(k)
声明： 总结学习，有问题或不当之处，可以批评指正哦，谢谢。