背包问题

背包问题是一类经典问题，经典的背包九讲、
推荐博客。
主要有0-1背包、完全背包、分组背包、多重背包。

0-1背包

0-1背包问题题目

0-1背包问题主要场景如下：
有N件物品和一个容量为V的背包。第i件物品的费用是C_i ，价值是 W_i 。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

0-1背包问题解题思路

276. 栅栏涂色

276. 栅栏涂色leetcode链接
题目描述：

像这种题目来说，是组合问题【后续有时间，把组合问题单独拿出来讲一下】。也就是从n个当中选k个，从n-1当中选k-1个，直至最后是从n-(n-1)个当中选k-(k-1)个的乘积。
对于动态规划来说，是一个经典问题，首先确定状态的定义，即：
dp[i] 用来表示i个栅栏柱的涂色的方案数，有两种情况：
如果：i与i-1的颜色相同，则表明i-1与i-2的颜色不同，则i的数目为dp[i-2]*(k-1)
如果：i与i-1的颜色不同，则i的数目为dp[i-1](k-1)
则递推公式为：
dp[i] = dp[i-2](k-1) + dp[i-1](k-1)