动态规划——浅谈dp如何入门,以及入门题目(值得收藏,持续更新,已更新01背包)

前言

动态规划如何入门?如果你问我怎么精通,那我只能告诉你我也不知道,但你要问我怎么入门,那我就可以和你说道说道了.

我并没有能力也不想说你看完就会了,我只是想给大家开个头,你只要知道怎么写了怎么去思考了,你就可以通过刷题来强化思维了,能走多远就看各位的造化了!

动态规划入门须知

动态规划（Dynamic Programming, DP）是一种通过将复杂问题分解为更小的子问题并解决这些子问题来构建解决方案的算法设计方法。动态规划的核心是状态转移方程，它定义了如何从一个或多个已知状态转换到一个新的状态。状态转移方程是动态规划问题的递推关系，用于描述当前状态与之前状态的关系。

想要做好一道动态规划题,或者说想要写所有的动态规划题,基本上都是按照这个步子走

1.设计状态表示

dp,其实也是记忆化存储,不过dp数组存的是题目需要你求的最优解(后续看题目来说)

在开始写代码之前,我们基本上要提前想要dp数组是一维的,二维的,还是三维的,然后呢,数组的值代表什么,这个真的很重要!!!!,基本上dp 数组的值,就是我们的答案

2.状态转移方程

什么叫状态转移方程呢,说实话,笔者也很为难,自己都是半桶水,还想教会别人.

通俗地说，状态转移方程就是一个规则或公式，告诉你如何从已知的信息（以前的结果）推导出未知的信息（当前的结果）。就像搭积木一样，你用之前已经搭好的积木，按照一定的规则，搭建出新的积木。

3.确定初始条件以及边界

在状态转移方程开始之前,总要有开始的值吧,而且有时候还会有一些边界值要你人为设置的.

4.代码实现(填表)

所有东西都构思好了,就要代码实现了

此时大概率,你的脑子或者草稿纸已经有一张表了,你能根据公式不断往表中塞值进去,这也是实现代码.

要判断好填表顺序,这也会决定你的循环要怎么写

你说上面都是写的什么玩意,我看不懂?没关系,看不懂就对了,因为我一开始也是蒙的,接下来

看一些题目吧,看完这些题目你还不会入门,那你来骂我好了                                                        

题目一

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

这题就是最简单的入门题,为什么?因为他已经告诉你状态转移方程了

 Tn+3 = Tn + Tn+1 + Tn+2

那么,我们的状态表示怎么写呢?

dp[] 数组应该这么表示  dp[i] 表示,第i个位置的泰波那契数的值

然后边界也以及告诉你了,T0 = 0, T1 = 1, T2 = 1.

所以说,我们就可以开始写了

class Solution {
public:
    int tribonacci(int n) 
    {
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        vector<int> dp(n+1);
        dp[0]=0,dp[1]=dp[2]=1;
       int a=0,b=1,c=1,d=0;
        for(int i=3;i<=n;i++)
        {
        //   d=a+b+c;
        //   a=b;
        //   b=c;
        //   c=d;
           dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
      return  dp[n];
    }
};

这个是常规写法,可以看到,每一步都是有迹可循的,按照上面的四步走写的

dp[] 数组应该这么表示  dp[i] 表示,第i个位置的泰波那契数的值

 Tn+3 = Tn + Tn+1 + Tn+2  是状态转移方程

  dp[0]=0,dp[1]=dp[2]=1; 是初始条件

最后实现代码

当然了,这里也有更优化的写法,就是滚动的数组

class Solution {
public:
    int tribonacci(int n) 
    {
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        vector<int> dp(n+1);
        dp[0]=0,dp[1]=dp[2]=1;
       int a=0,b=1,c=1,d=0;
        for(int i=3;i<=n;i++)
        {
          d=a+b+c;
          a=b;
          b=c;
          c=d;
        }
      return  d;
    }
};

这里 a,b,c,d就好像一个滚动的桶,一直在往前走,然后最后d 就是答案.

题目二

LCR 088. 使用最小花费爬楼梯 - 力扣（LeetCode）

这题就稍微稍微有点难了

状态表示

首先,我们的状态表示最好是根据答案来的,答案要我们求最小花费.                              

那我们的dp数组怎么表示呢  还是 dp[i],一维数组,我们可以这么看,dp[i] 表示 如果你需要走到第 i 个台阶,所需要的最小花费,那么我们就可以记数组的大小为 n, 然后dp[n] 就是我们的答案

转移方程

我第 i 个的花费源于哪里?不是第 i-1 个台阶 就是第 i-2个台阶吧,我们只要取这两个的最小值加起来,是不是就可以表示,这是最小花费了?

还是不太懂大伙可以看图

cost 数组是台阶花费数组

我是花费x 走到 n 呢,还是花费y 走到 n 呢? 那就看谁更小了,然后加上原本的花费,别忘了

dp[] 表示花费

dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

边界设置

这题没什么需要在意的,就是正常写就可以了,一开始dp 数组都是0

需要注意的是,我们是每个台阶都会算到的,所以不用担心说什么哎呀我某个台阶会不会没算到啊

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost)
{
  int  n=cost.size();
 
  vector<int> dp(n+1);
 
  for(int i=2;i<=n;i++)
  {
    dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
  }
  return dp[n];
    }
};  

01背包问题

ok,今天开始继续更新,虽然这部分分开写,能有更多的流量,但是,为了可能没有的读者们,也为了我自己以后方便回顾,我还是写在一起吧!!!!!!!

什么是01背包?

1.求解 01 背包问题 - 蓝桥云课 (lanqiao.cn)

请看图

刚刚介绍的题目,都可以用简单的一维dp 数组解决,那么01背包就不能了, 背包问题以及衍生出来的一些问题,笔者认为,都有这么小小的特征吧,在某种条件下的某种最优解,笔者这里写了两个某种,你如果用一个一维dp 数组表示状态,肯定没法这么巧妙的,所以我们用了二维dp 数组.

这道题如果由人来思考,我们会怎么思考?肯定是直接看最大承重多少,然后再去选择最有价值的物品

但是计算机可以吗?那肯定不行啊,我们的脑子是直接跳到最大承重了,但是计算机不行啊,所以我们要从0开始,看看不同承重能获得的最大价值

状态表示

所以的所以 ,dp[i][j]表示,在前i个物品,容量不超过j的情况下,背包物品的最大价值

状态转移方程

我们可以这么看

    for(i=1;i<=N;i++)//依次遍历从第1个物品到第N个物品
    {
        for(j=1;j<=V;j++)//依次遍历从0~背包容量V
        {
            dp[i][j]=dp[i-1][j];
            // 不选i.
            if(j>=v[i])
            {
              dp[i][j]=max(dp[i][j],w[i]+dp[i-1][j-v[i]]);
              // 选i
            }
        }
    }

我们先从只有一个物品开始推,然后呢,遍历容量, 到达这么一个效果: 我的 dp[i][j]  就是前i个物品在j容量下能得到的最大价值 

dp[i][j]=max(dp[i][j],w[i]+dp[i-1][j-v[i]]);

目光依旧看到这个方程这里.

问题可以转化为从i-1件物品装入容量为j的背包最大价值，再加上第i件物品的价值. 前提是,能装,

如果可以装,那么就是这个 物品的价值,加上    "在减去这个物品需要的体积的剩余体积下,前i-1个物品的最大价值" ,这个值,我们前面肯定已经算出来了,因为表是一路填过来的,这个值肯定已经存在数组里面了.

这里也体现了,为什么我们要依次遍历0-V容量时,背包能装的最大价值,这也是我们需要的数据

然后呢,再和不选这个第i个物品,(也就是不装, 上面是装的情况.)进行比较,看看谁的值大!

始终记住,二维数组表示的是我们要的结果,即 在容量j下,放置前i个物品能得到的最大值,下然后去看代码

边界设置

不需要额外去设置,默认价值都是0

代码演示

完整代码如下

#include <iostream>
# include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];
// dp[i][j]表示,在前i个物品,容量不超过j的情况下,背包物品的最大价值
int v[1010],w[1010];//体积和价值
int main(){
    int N,V;
    int i,j;
    //输入数据
    cin>>V>>N;//商品个数和背包容量
    for(i=1;i<=N;i++)
    {
        cin>>v[i]>>w[i];//体积和价值
    }
    for(i=1;i<=N;i++)//依次遍历从第1个物品到第N个物品
    {
        for(j=1;j<=V;j++)//依次遍历从0~背包容量V
        {
            dp[i][j]=dp[i-1][j];
            // 不选i.
            if(j>=v[i])
            {
              dp[i][j]=max(dp[i][j],w[i]+dp[i-1][j-v[i]]);
              // 选i
            }
        }
    }
    cout<<dp[N][V]<<endl;//输出前N个商品,背包容量为V的最优解
    return 0;
}

笔者想说的

笔者在写01背包问题时,也苦恼很久,不知道如何去说明这个问题,话到嘴边却说不出去,如鲠在喉 .

当今学习这种基础算法已经有很多条件了,看视频自然是最好的学习方式,但笔者还是想写,虽然也没什么人看就是了. 

2024.6.7更新............

杨辉三角问题 

笔者又来更新了.今天更的是杨辉三角问题

118. 杨辉三角 - 力扣（LeetCode）

先给答案代码(Java 版本 )

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(1);
        ret.add(firstRow);
        for (int i = 1; i < numRows; i++) {
            List<Integer> newRow = new ArrayList<>();
            newRow.add(1);  // 每行开头的 1
            List<Integer> previousRow = ret.get(i - 1);
            for (int j = 1; j < i; j++)
             {
                int num = previousRow.get(j - 1) + previousRow.get(j);
                newRow.add(num);
            }    
            newRow.add(1);  // 每行结尾的 1
            ret.add(newRow);
        }
        return ret;
    }
}

1.状态表示

题目要求我们给出前N行完整的杨辉三角

那我们就顺从他,返回一个完整的杨辉三角,我们用list 建一个二维数组 ret 表示杨辉三角

2.状态转移方程

题目已经给我们了

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

你也许会问:"哎呀这是一个三角形啊,数组怎么放呢?",那你应该这么看了

他看似是一个三角形,实际上还是二维数组,其他位置放置的是0而已,更好了,压根不需要边界设置了

转移方程由题意也能知道

看图,这显示了填表过程

转移方程如下

 int num = previousRow.get(j - 1) + previousRow.get(j);

3.边界设置

只需要每次在数组头和尾加上一个 1 就好了,其他默认是0也不需要额外设置

4.代码演示(填表)

在上面了,为了水点字我再发一次

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<List<Integer>> generate(int numRows) 
{
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(1); 每一行第一个数字都是1
        ret.add(firstRow);
        for (int i = 1; i < numRows; i++) {
            List<Integer> newRow = new ArrayList<>();
            newRow.add(1);  // 每行开头的 1
            List<Integer> previousRow = ret.get(i - 1);
           得到上一行的数字,便于进行取值填进状态转移方程
            for (int j = 1; j < i; j++)
             {
                int num = previousRow.get(j - 1) + previousRow.get(j);
                newRow.add(num);
            }    
            newRow.add(1);  // 每行结尾的 1
            ret.add(newRow);
        }
        return ret;
    }
}
 
 

填表顺序大致是从上到下,从左往右

更新于6.12号

结尾

今天暂时就写那么多,笔者的语言组织能力还是弱了点.有人看最好没人看拉倒,反正这也算是我的复习资料