动态规划

前言

​ 前一个月开始刷题，那会儿在力扣上面，见一个DP题一个不会的。突然觉得自己好垃圾哈哈哈。为什么现在写这个呢，就刚刚刷着刷着题，突发奇想了，觉得好像找到了哪个感觉？开始刷DP过瘾了哈哈哈。但是我又不太会讲，直接来分享我对一些DP案例题的解题思路。不多说，进入正题。

案例(其他几个案例整理出来后补上)

青蛙跳级问题

一个青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法。

思考

1. 青蛙跳级的方式有2种：

   • 跳1个台阶
   • 跳2个台阶

2. 将问题转变为数学函数：
   

解题

class Solution {
    public int climbStairs(int n) {
        int[] res = new int[n+1];
        if(n <= 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        res[0] = 0;
        res[1] = 1;
        res[2] = 2;
        for(int i = 3; i <= n; i++){
            res[i] = res[i-1] + res[i-2];
        }
        return res[n];
    }
}

拓展

• 如果小青蛙有三种跳法呢？跳一个台阶、跳两个台阶、跳三个台阶呢？

• 斐波那契数列

• 力扣72题

背包问题

假如你有一个可以装5kg的背包，你去商城里面得将最有价值的物品装进背包，但是不能超过背包容量。求你能带走的最大价值的总和

商场中的物品有：

物品	重量	价值
铅笔	0.5kg	1
面包	1kg	3
手电筒	3kg	10
水	2kg	7

思考

平常我们遇到这种问题，都是想着先把性价比最高的拿了，然后拿第二的，但是在某些场景下就不太适合了。这里就不太过多讲解，主要使用动态规划来解这道题目。

物品	0.5kg	1kg	2kg	3kg	4kg	5kg
铅笔	1	2	4	6	8	10
面包	1	3	6	9	12	15
手电筒	1	3	6	10	13	16
水	1	3	7	10	14	17

主要思路：将每一阶段重量的最优解保存

例如：

• 当只有铅笔的时候： 0.5kg的最优解是1、1kg的最优解是2……5kg的最优解是10
• 当有铅笔和面包的时候：0.5kg的最优解是1、1kg的最优解是3……5kg的最优解是15
• ……
• 当全部物品都在时：0.5kg的最优解是1、1kg的最优解是3……5kg的最优解是17

我们这时就能得到最终答案为17