大数据最全【数据结构与算法】之动态规划经典问题_动态规划问题，2024年最新自学者福利

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上大数据知识点，真正体系化！

由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新

需要这份系统化资料的朋友，可以戳这里获取

(

n

)

=

{

0

,

n

=

0

−

1

,

n

<

0

m

i

n

(

f

(

n

−

c

o

i

n

)

)

1

,

n

0

f(n)=

$$\begin{cases} 0,n=0\ -1,n<0 \ min(f(n-coin))+1,n>0 \end{cases}$$

f(n)={0,n=0 −1,n<0min(f(n−coin))+1,n>0​

代码如下：

    /\*\*
 \* 计算出能组成总金额的最少硬币数量
 \* @param coins 给定的硬币的面额
 \* @param amount 给定的总金额
 \* @return 最少的硬币数量
 \*/
    public static int coinChange(int[] coins, int amount){
        if(amount == 0) return 0;
        if(amount < 0) return -1;

        // 核心：
        // 1、求总金额为16的结果 【1，3，5】
        // 2、【1】找到15的最优解+1 ---- 【3】找到13的最优解+1 ----- 【5】找到11的最优解+1
        // 3、取最小值
        int result = Integer.MAX\_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int subMin = coinChange(coins, amount - coins[i]);
            // 如果最优解不存在 -1 继续
            if (subMin == -1) continue;
            if(subMin + 1 < result){
                result = subMin +1;
            }
        }
        return result == Integer.MAX\_VALUE ? -1 : result;

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

在此过程中，我们确实会出现很多的重复子问题计算，我们需要使用一个memo备忘录进行记录。

private static int changeCoin2(int[] coins,int amount,int[] memo){
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    int res = Integer.MAX\_VALUE;

    for (int i = 0; i < coins.length; i++) {
        // 遍历子问题，假设amount为10元，如果有了一个2元，剩下的8元最少需要几个呢？，子问题就是8元所需要的个数
        // 同理8元所需要的个数可以使用递归完成
        int subProblem = Integer.MAX\_VALUE;
        if(amount-coins[i] >= 0 && memo[amount-coins[i]] != 0){
            subProblem = memo[amount-coins[i]];
        } else {
            subProblem = changeCoin2(coins,amount-coins[i],memo);
        }

        // 子问题有误解的时候，比如子问题的金额小于硬币的最小金额
        if(subProblem == -1) continue;
        // 我们的最优结果就是，最优的子问题的最优解+1
        res = Math.min(res,1 + subProblem) != Integer.MAX\_VALUE ? Math.min(res,1 + subProblem):-1;
    }
    memo[amount] = res;
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

最后比较一下有【备忘录】和没有【备忘录】的性能差异：

public class Change {
	...
    public static void main(String[] args) {

        long start = System.currentTimeMillis();
        System.out.println(changeCoin2(new int[]{1,2,3},100,new int[100+1]));
        long end = System.currentTimeMillis();
        System.out.println(end - start);

        start = System.currentTimeMillis();
        System.out.println(changeCoin(new int[]{1,2,3},100));
        end = System.currentTimeMillis();
        System.out.println(end -start);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

三、0-1背包问题

题目： 有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。

0-1背包问题： 在最优解中，每个物品只有两种可能的情况，即在背包中或者不在背包中（背包中的该物品数为0或1），因此称为0-1背包问题。

子问题： 子问题必然是和物品有关的，对于每一个物品，有两种结果：能装下或者不能装下。

• 第一，包的容量比物品体积小，装不下，这时的最大价值和前i-1个物品的最大价值是一样的。
• 第二，还有足够的容量装下该物品，但是装了不一定最大价值，所以要进行比较。由上述分析，子问题中物品数和背包容量都应当作为变量。

因此，子问题确定为背包容量为j时，求前i个物品所能达到最大价值。

确定状态： 由上述分析，“状态”对应的“值”即为背包容量为j时，求前i个物品所能达到最大价值，设为dp[i][j]。初始时，dp[0][0]为0，没有物品也就没有价值。

确定状态转移方程： 由上述分析，第i个物品的体积为w,价值为v，则状态转移方程为

f

(

n

,

v

)

=

{

f

(

n

−

1

,

v

)

,

w

e

i

g

h

t

[

i

]

j

（

装

不

下

）

M

a

t

h

.

m

a

x

(

f

(

i

−

1

,

j

−

w

e

i

g

h

t

[

i

]

)

v

a

l

u

e

[

i

]

,

f

(

i

−

1

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上大数据知识点，真正体系化！

由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新

需要这份系统化资料的朋友，可以戳这里获取

)

v

a

l

u

e

[

i

]

,

f

(

i

−

1

[外链图片转存中…(img-ZwSbP4oH-1715040137305)]
[外链图片转存中…(img-j0B7jU2i-1715040137305)]
[外链图片转存中…(img-J7wR7GJY-1715040137306)]

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上大数据知识点，真正体系化！

由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新

需要这份系统化资料的朋友，可以戳这里获取