0%

Dynamic Programming

最近在复习DP的知识点, 所以昨天做了3道题.

  1. Coin Change, python3, 提交 run time 1057 ms. 时间O(n), 空间O(n). 思路是dp[n]数组, 最后兑换dp[k]代表需要兑换k块钱需要的最小硬币数, dp[k] = min( dp[k-s1], dp[k-s2]…) +1. s1,s2为题目提供的硬币选项. 代码corner case, k-s <0是dp[k-s]为max_int, dp[0]为0. max_int 代表无法兑换.

  2. Jump Game, python3, 提交 run time 403ms. 时间O(n^2), 空间O(n). 思路: 用dp[n]代表能否跳到n的位置. 这时候有两个array,dp[n] 和A[n]. dp[k]为true的条件, 从0到k-1中,至少有一个dp[s]为true 且 A[s] > (s到k的距离). 所以在一个0-k的forloop里面, 还有一个0-k-1的小loop. 这题还可以用greedy做.. 还没有做.

  3. Maximum Product Subarray, python3, 提交1441ms. 时间O(n), 空间O(n).思路: 求连续的最大积, 按照dp的思路. 第n个数的积是否最大, 求自product[n-1] K[n]是否最大, 如果product[n]要大于product[n-1]其实就代表这个部分数组是继续同符号增加. 如果product[n] < product[n-1], 其实就是符号变负数了. product[n] = K[n]重新算起.. product[n]= max(product[n-1]\K[n], K[n]) 这里需要处理的是, 如果后面还有一个负数出现,负负得正的情况,所以我们还需要一个neg_product的数组来维护负值的product. 所以

    product[n] = max(max(product[n-1]*K[n], neg_product[n-1]*K[n]), K[n])
    neg_product[n] = min(min(product[n-1]*K[n], neg_product[n-1]*K[n]), K[n])

    最后找product里的最大值