玉兔月圆时刻：动态规划中的月饼传递趣谈

我正在参加中秋创意投稿大赛，详情请看：中秋创意投稿大赛

引入

马上就到中秋节了，嫦娥姐姐派下凡间的玉兔要带着在人间收集的月饼回广寒宫交差了，但是回去的路上会有层层险阻。因为玉兔和嫦娥姐姐一样爱美，所以体力上会有不足，每次最多走两步就要停下来歇一歇，但是这时强盗就会趁虚而入，把玉兔的月饼抢走一部分，你能帮嫦娥姐姐保留更多的月饼吗？

任务描述

一共有i个台阶，玉兔需要顺利通过这i个台阶才能将月饼送给嫦娥，每个台阶后面都藏有强盗，每个强盗能抢的月饼数量各不相同，有多有少，需要你求出玉兔通过这些台阶损失最少的月饼。

图示

解题思路

学过组合数学的同学可能很快就会想到帮助玉兔的方法了，到达第i个台阶损失的月饼最少，有两种方案可以选择：（1）到达第i个台阶损失的月饼最少，然后再走一步就可以见到嫦娥姐姐；（2）到达第$i-1$个台阶损失的月饼最少，然后走两步（第i个台阶不停下来）同样可以见到嫦娥姐姐。所以顺利把月饼送到嫦娥姐姐手中的最小损失是可以表示为$minLost[i] = min(dp[i],dp[i-1])$。为了求出到达嫦娥姐姐身边的最小损失，我们可以分别先算出玉兔到达第i个台阶和第$i-1$个台阶的最小损失，用dp[i]与dp[i-1]表示，然后再通过$min(dp[i],dp[i-1])$来求出到达嫦娥姐姐身边的最小损失。

代码描述

public static int minLostDP1(int[] lost){
    int[] dp = new int[lost.length];
    // 初始状态
    dp[0] = lost[0]; // 走第0个台阶
    // 走第1个台阶 (先走第0个，在走第1个 ;或是直接走第1个)
    dp[1] = Math.min(lost[1] ,lost[0]+lost[1]);
    for (int i = 2; i < lost.length; i++) {
        //状态转移方程
        dp[i] = Math.min(dp[i - 2], dp[i - 1]) + lost[i];
    }
    return Math.min(dp[lost.length - 2], dp[lost.length - 1]);
}

算法优化

基于上面的解法，我们还可以进一步进行优化。这里使用的dp数组来记录每一层丢失的月饼数量，我们可以使用两个指针p与q以轮转的方式代替dp数组。

代码描述

public static int minLostDP(int[] lost){
    int tmp,p=0,q=0;
    for(int i =2;i<lost.length;i++){
        tmp = q;
        // 状态转移方程
        q = Math.min(lost[i-2]+p,lost[i-1]+q);
        p = tmp;
    }
    return  q;
}

任务完成

在你的帮助下，玉兔已经顺利完成了任务，嫦娥姐姐也能如愿的品尝到人间的美味，一起期待着中秋节的到来吧！

完整代码

public class JueJin {
    public static void main(String[] args) {
        int[] lost = new int[]{1,2,1,2,1,2};
        int minLost = minLostDP(lost);
        System.out.println(minLost);
    }
    public static int minLostDP(int[] lost){
        int[] dp = new int[lost.length];
        // 初始状态
        dp[0] = lost[0]; // 走第0个台阶
        // 走第1个台阶 (先走第0个，在走第1个 ;或是直接走第1个)
        dp[1] = Math.min(lost[1] ,lost[0]+lost[1]);
        for (int i = 2; i < lost.length; i++) {
            //状态转移方程
            dp[i] = Math.min(dp[i - 2], dp[i - 1]) + lost[i];
        }
        return Math.min(dp[lost.length - 2], dp[lost.length - 1]);
    }
    public static int minLostDP1(int[] lost){
        int tmp,p=0,q=0;
        for(int i =2;i<lost.length;i++){
            tmp = q;
            // 状态转移方程
            q = Math.min(lost[i-2]+p,lost[i-1]+q);
            p = tmp;
        }
        return  q;
    }
}

总结

对于求解最值问题，我们首先想到的就是暴力穷举方法，暴力法虽然能解决问题，但是效率是非常低的。这时我们可以从动态规划的角度考虑这些问题。

动态规划中的穷举有以下特点：

• 存在重叠的子问题;
• 一定具有最优子结构，这样才能通过子问题的最值得到原问题的最值；
• 需要dp数组来进行优化;
• 只有列出正确的状态转移方程，才能正确的穷举。

其中重叠子问题、最优子结构、状态转移方程又称为动态规划的三要素。

遇到动态规划的问题可以从这三要素入手，相信很快就可以摆脱暴力法解题的思路。

以上为个人理解以及总结，有不对的地方还请各位大佬指正。最后提前祝大家中秋节快乐！！！