#华为机试# 华为9.1机试第一题动态规划
动态规划解决。
Javascript和python的代码，写了注释
输入输出处理省略
总体就是用dp表储存到达某个节点处两次传递的状态，[第一次的传出数量，第二次的传出数量]，然后因为节点可能坏掉，那么节点i处的上一个传来节点可能是i-1或者i-2（i-2即i-1处的节点坏掉了，这样能保证没有连续的节点坏掉），取这两种情况下i处能够传递的总数量最小的那种情况记录i的状态；
然后就是理清楚如何从i-1或者i-2的状态得到i，就是下面的cal()函数完成的工作。
只需要一次遍历，最后输出n-1和n处的较小的那个即可。
只需要一次遍历，最后输出n-1和n处的较小的那个即可。
let n = 3, a = 100, capability = [[50, 30], [40, 30], [20, 10]] // 测试数据
function main(n, a, capability) {
if (n < 1) return a
let dp = [[a, 0]] //dp[i]为[第一次传递时从i发送的数量,第二次传递时从i发送的数量],最初传来的a可以相当于是从一个最大传送量无限，最大储存量为0的节点传过来的
dp[1] = cal(dp[0], capability[0])
for (let i = 2; i <= n; i++) {
let res1 = cal(dp[i - 1], capability[i - 1]) //上一个没坏，从上一个传来
let res2 = cal(dp[i - 2], capability[i - 1]) //上一个坏掉了，从上上个传来
dp[i] = res1[0] + res1[1] <= res2[0] + res2[1] ? res1 : res2 //状态转移，选择值最小的一种传递方案
}
return Math.min(dp[n][0] + dp[n][1], dp[n - 1][0] + dp[n - 1][1]) //第n个节点和第n-1个节点中传出值较小的一个，后一个相当于最后一个节点坏了
}
function cal(pre, cap) { //通过dp[i-1]或者dp[i-2]的状态来计算现在的可能值：pre为第i-1或者i-2个节点处两次传递发出的数量（[第一次，第二次]）；cap为i处的传输能力，即[最大发送量,最大储存量]
let send1 = Math.min(pre[0], cap[0]) //第一次传递时从i发送的数量
let temp = pre[0] > cap[0] ? pre[0] - cap[0] : 0 // 第一次传递时从i传出后剩的数量(因为有可能i的可发送数量大于传过来的数量，那么就剩下0)
let send2 = Math.min(temp + pre[1], cap[1] + pre[1], cap[0]) //第二次传递时从i发送的数量
return [send1, send2]
}
let res = main(n, a, capability) 注：对之前的代码进行了一点修改，pre[0] 有可能小于 cap[0]，如果pre[0] <=cap[0]，上一次传递在i处剩下来的应该是0 let temp = pre[0] > cap[0] ? pre[0] - cap[0] : 0 // 第一次传递时从i传出后剩的数量(因为有可能i的可发送数量大于传过来的数量，那么就剩下0)
补充：再贴一个python的代码
n = 3 a = 100 capability = [[50, 30], [40, 30], [20, 10]] # 测试数据 # 动态规划主函数 def main(n, a, capability): if(n<1): return a dp = [[a,0]] #dp[i]为[第一次传递时从i发送的数量,第二次传递时从i发送的数量],最初传来的a可以相当于是从一个最大传送量无限，最大储存量为0的节点传过来的 dp.append(cal(dp[0],capability[0])) #通过dp[0]计算dp[1] for i in range(2,n+1): res1 = cal(dp[i-1],capability[i-1]) #上一个没坏，从上一个传来 res2 = cal(dp[i - 2], capability[i - 1]) #上一个坏掉了，从上上个传来 temp=res1 if(res1[0]+res1[1]<=res2[0]+res2[1]) else res2 #状态转移，选择值最小的一种传递方案 dp.append(temp) #dp[i] return min(dp[n][0]+dp[n][1],dp[n-1][0]+dp[n-1][1]) #第n个节点和第n-1个节点中传出值较小的一个，后一个相当于最后一个节点坏了 #通过dp[i-1]或者dp[i-2]的状态来计算现在的可能值：pre为第i-1或者i-2个节点处两次传递发出的数量（[第一次，第二次]）；cap为i处的传输能力，即[最大发送量,最大储存量] def cal(pre,cap): send1 = min(pre[0], cap[0]) #第一次传递时从i发送的数量 temp = pre[0] - cap[0] if(pre[0] > cap[0]) else 0 # 第一次传递时从i传出后剩的数量(因为有可能i的可发送数量大于传过来的数量，那么就剩下0) send2 = min(temp+ pre[1], cap[1] + pre[1], cap[0]) #第二次传递时从i发送的数量 return [send1,send2] res=main(n, a, capability)
查看11道真题和解析