algorithm - 了解动态规划中的基本案例

Question

考虑这个问题计数的不同方式 express-n sum-1-3-4

我的理解是 f(n) 是将 n 表示为 1、3 和 4 之和的方法数

f(n-1) 是将 n-1 表示为 1、3 和 4 之和的方法数

f(1) 是将 1 表示为 1、3 和 4 之和的方式数

f(0) 是将 0 表示为 1、3 和 4 之和的方式数

不应该是 0，因为没有办法将 0 表示/表示为 1,3,4 的总和

刚开始学习动态编程，但我不明白为什么这应该是 1 而不是 0

标签： algorithmdynamic-programming

Answer 1

好吧，假设您想将某个总和 S 表示为 1、3 和 4 的总和

你可以用数学方法把它写成等式S = 1*x + 3*y + 4*z，其中 x,y,z 表示总和中的一、三和四的数量。

所以现在f(S)只是方程解的数量（记住 x,y,z 是非负整数）

当S=0我们可以很容易地看到这个方程有一个解时——x=0, y=0, z=0