博客

ps：记录在动态规划上踩过的一个大坑~

今日时间为2021.4.26，习俗性打开leetcode每日一题，先给出该题题目：

标题：1011. 在 D 天内送达包裹的能力


传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。


示例1：





示例二：

刚看到这个题的第一反应就是求极小值问题：动态规划。然后开始思考动态规划的解法，发现题目中总共存在着两个状态，**分别是剩余的天数和当前传送了多少个包裹，**因此是一个二维动态规划问题。仔细一想之后发现边界条件等有点复杂，但是还是硬着头皮做下去，做了足足40分钟，

利用二维动态规划结合前缀和数组算法写出了第一个版本的动态规划代码

，代码测试案例均没有问题，代码和注解如下：

class Solution {
   
    public int shipWithinDays(int[] weights, int D) {
   
        /*
            dp[i][j]:i:当前准备床送第i个包裹   j:还剩j天  最小承重
            dp[i][j] = max(sum(i-k到i-1),dp[i-k][j-1])
            求解值为：dp[0][D]
            初始化:dp[len][0] = 0; dp[i][0]=-INF  i+j>len -INF
        */
        int len = weights.length; 
        int[] sums = new int[len+1];//计算前缀和  sum[i] = weights[0]+...+weights[i-1];  weights[i-j] = sum(j+1)-sum[i];
        int sum = 0;
        for(int i=0;i<len;i++){
   
            sum+=weights[i];
            sums[i+1] = sum;
        }
        int[][] dp = new int[len][D+1];
        for(int j=1;j<=D;j++){
   //从还剩1天开始
            for(int i=0;i<len;i++){
   //当前需要从i开始拿去
                if(j==1){
   //还剩一天的情况比较特殊，这时必须全部取完
                    dp[i][j]