说到动态规划，我们应该先了解一个概念：
无后效性：无后效性是指如果在某个阶段上过程的状态已知，则从此阶段以后过程的发展变化仅与此阶段的状态有关，而与过程在此阶段以前的阶段所经历过的状态无关。利用动态规划方法求解多阶段决策过程问题，过程的状态必须具备无后效性。
说通俗一点就是要解决一个问题的时候，其子问题必须全部被解决。
我认为动态规划分为两种类型：第一种：用来记录递归变量的变化状态，写出递归基本上就写出了动态规划。这种情况一般情况下第一个位置是用来遍历的，第二个，第三个等位置是题目的限制条件，而dp表本身的含义是在第一个参数和第二个参数的情况下，我们的答案是多少。以上所说我认为dp表的含义和题目的限制条件没有强关联性才可以。什么叫强关联性，例如01背包问题，题目的限制条件是背包的重量不可以超重，而要求是最大价值。这就不具有强关联性。再反观砝码问题，题目没有限制条件，只是问你能称多少种重量，也就是说，我的dp表确实需要第二个参数，但是这第二个参数并不是限制条件，这种情况下，dp表一般是第二个位置是否保存了某个值为参考标准，有就是1，没有就是0。这样的题目属于第二种，我们认为dp表不是记录递归变量的变化状态的。而是它本身就跟结果有关。
这些理论只是初步想法，我们用题目来验证：
砝码问题
题目描述
你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, · · · , WN。 请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数 N。 第二行包含 N 个整数：W1, W2, W3, · · · , WN。
样例输入输出
【样例输入】 3 1 4 6 【样例输出】 10
思路分析：一看到题目，我的想法就是从暴力递归到动态规划，一个index变量用来遍历，再用一个限制条件。但是突然我发现题目的限制条件不存在，只是说随意怎么放砝码，能称量出多少种重量。也就是说变量有2个，一个是index下标，一个是重物的重量，但是重物的重量没有任何限制。因此我想到了暴力递归dfs，再用一个hashmap来保存这个重量是否出现过，然后计算一共出现了多少种重量。因此有了以下代码
我们定义递归含义是：在[0, index]区间范围之内的砝码可以称量出重量sum吗？
或者说，这个递归没有严格的含义，它就是一共穷举行为，一共dfs遍历。
#include<iostream>
#include<unordered_map>
#include<math.h>
using namespace std;
unordered_map<int, int> m;
int N;
void dfs(int index, int sum, int w[])//index是下标遍历，sum是目前重物的重量
{
? ?if(index == N)
? {
? ? ? ?m[sum]++;
? ? ? ?return ;
? }
? ?dfs(index + 1, sum + w[index], w);//放砝码目前重物改变
? ?dfs(index + 1, sum, w);//我不要这个重物
? ?dfs(index + 1, fabs(sum - w[index]), w);
}
int main()
{
? ?cin >> N;
? ?int*w = new int[N + 1];
? ?int sum = 0;
? ?for(int i = 0; i < N; ++i)
? {
? ? ? ?cin >> w[i];
? ? ? ?sum += w[i];
? }
? ?dfs(0, 0, w);
? ?int ans = 0;
? ?for(int rest = 1; rest <= sum; rest++)
? {
? ? ? ?if(m[rest] >= 1)
? ? ? {
? ? ? ? ? ?ans++;
? ? ? }
? }
? ?cout << ans <<endl;
? ?return 0;
}
当然，暴力会超出时间限制的。我们是不是可以考虑一下剪枝？我觉得没必要，这道题也不好剪枝。
有几个值得注意的点：
1.为什么要加上绝对值？
答：因为就算重量减成负数了，那么把重物放在另外一边就可以了，这是可以自由选择的，我们没有规定重物必须在哪一边。sum + w[index]表示的是我可以通过加砝码，我不知道加在哪一边，可以算出sum + w[index]重量的物品，-也是一样，同理。
接下来使用动态规划的思路：
定义dp[i] [j],i表示index，用于遍历，j表示目前可以称量出来的重物，dp表示能否装得下这个重物，装得下就算1，装不下就算0.
从第一个角度来看
我在[0, 0]范围之内可以称量出w[0]的重物，按照测试用例也就是1
[0, 1]范围内可以称量出1， 1 + 4， |1 - 4| 4也就是1 3 5 4
[0, 2]范围额可以称量出1 3 5（继承过来） 3 + 4 |3 - 4| 5 + 4 |5 - 4|也就是1 3 5 7 9 4....
.......
以此类推，按照这个思路，我们写出动态规划的代码：
#include<iostream>
#include<math.h>
using namespace std;
int N;
int dp[110][10010];
int main()
{
? ? cin >> N;
? ? int* w = new int[N + 1];
? ? int sum = 0;
? ? for(int i = 0; i < N; ++i)
? ? {
? ? ? ? cin >> w[i];
? ? ? ? sum += w[i];
? ? }
? ? dp[0][w[0]] = 1;
? ? for(int index = 1; index < N; index++)
? ? {
? ? ? ? //先把上一级的可以称量的状态继承过来
? ? ? ? for(int j = 1; j <= sum; ++j)
? ? ? ? {
? ? ? ? ? ? dp[index][j] = dp[index - 1][j];
? ? ? ? }
? ? ? ? //传入这一级一共砝码可以单独称量的的状态
? ? ? ? dp[index][w[index]] = 1;
? ? ? ? //更新这一级的状态
? ? ? ? for(int j = 1; j <= sum; ++j)
? ? ? ? {
? ? ? ? ? ? if(dp[index - 1][j] == 1)//上一级有解才能加减
? ? ? ? ? ? {
? ? ? ? ? ? ? ? dp[index][j + w[index]] = 1;
? ? ? ? ? ? ? ? dp[index][(int)fabs(j - w[index])] = 1;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? int ans = 0;
? ? for(int j = 1; j <= sum; ++j)
? ? {
? ? ? ? if(dp[N - 1][j] == 1)
? ? ? ? {
? ? ? ? ? ? ans++;
? ? ? ? }
? ? }
? ? cout << ans << endl;
? ? return 0;
}总结：
这个动态规划很诡异，它的dp含义记录的是是否存在dp的第二个参数，这对应我们所说的第二种dp吧。
走楼梯进阶
题目描述
楼梯有 nn 阶，上楼可以一步上一阶，也可以一步上二阶。
但你不能连续三步都走两阶，计算走到第nn阶共有多少种不同的走法。
输入格式
一行，一个数字，表示nn。
输出格式
输出走楼梯的方式总数。
暴力思路：
#include<iostream>
using namespace std;
//递归含义是[index, n]且此时正好走了x次二级台阶的方法数。很显然题目没有指定要走多少次x级台阶，
//但是我们知道index = 0的时候必定是走了0次
int process(int n, int index, int x)//x表示我连续走了几次二级台阶了
{
if (x == 3)
{
return 0;//如果x进化了3了，这个方法算作错误
}
if (n == index)
{
return 1;//如果走到第n级台阶的话，那么就说明方法数是1
}
else if (n < index)
{
return 0;//走超了，错误
}
int ways = 0;
ways += process(n, index + 1, 0);//如果遇到走一级台阶就清空为0
ways += process(n, index + 2, x + 1);//如果遇到二级台阶才把这个x进行++
return ways;
}
int main()
{
int n = 0;
cin >> n;
int number = 0;
number = process(n, 0, 0);//代表从第0阶台阶开始爬楼梯
cout << number << endl;
return 0;
}这个暴力时间很长，不做过多的阐述，很简单。
动态规划解析：
一维dp
错误案例剖析：
#include<iostream>
using namespace std;
long long dp[51];
int main()
{
int n = 0;
cin >> n;
dp[0] = 1;
dp[1] = 1;
for (int index = 2; index <= n; index++)
{
if (index < 6)
{
dp[index] = dp[index - 1] + dp[index - 2];
}
else
{
dp[index] = dp[index - 1] + dp[index - 2] - dp[index - 6];
}
}
cout << dp[n];
return 0;
}错误思路：我的可能性是走一级台阶，或者两级台阶的可能性之和，再减去一次性走6级台阶，但是这个思路严重错误了，因为你没有考虑到当一次性走6级台阶的index - 6的时候可能它本身就已经走了一级或者两级2级台阶了，所以如果我们这么减的话那么会减多了情况。
也就是说，我们要让它在index - 7的位置必须走一步到达index - 6的位置再连续走6步才可以。
代码如下：
#include<iostream>
using namespace std;
long long dp[51];
int main()
{
int n = 0;
cin >> n;
dp[0] = 1;
dp[1] = 1;
for (int index = 2; index <= n; index++)
{
if (index < 6)
{
dp[index] = dp[index - 1] + dp[index - 2];
}
else if (index == 6)
{
dp[index] = dp[index - 1] + dp[index - 2] - 1;//这里必须要单独讨论了，减去1即可
}
else
{
dp[index] = dp[index - 1] + dp[index - 2] - dp[index - 7];
}
}
cout << dp[n];
return 0;
}但是我们发现这样有点牵强，这个一维dp
因此我们这样写：
利用这个思路：
这里借用一下大佬的思路，这不是我的思路，这不是我的思路，这不是我的思路
二维dp
我们用第二个参数x，来记录是否连续走了x阶台阶。
代码如下：
#include<iostream>
using namespace std;
long long dp[60][5];
int main()//发散开而不是收回去
{
?? ?int n = 0;
?? ?cin >> n;
?? ?long long ans = 0;
?? ?dp[0][0] = 1;//走0级1个方法
?? ?dp[1][0] = 1;//走1级一个方法,因为才开始，所以我们知道x(连续走了x次二级台阶)一定是0，这里的x不可能为1或者2
?? ?for (int index = 2; index <= n; index++)
?? ?{
?? ??? ?//走一步
?? ??? ?dp[index][0] = dp[index - 1][0] + dp[index - 1][1] + dp[index - 1][2];//走一步需要index - 1的状态，而index - 1状态的时候可能一级连续的走过2级了，所以要加起来。然后x被清0，一定是0.
?? ??? ?//走两步
?? ??? ?dp[index][1] = dp[index - 2][0];//如果要走两部的话，这里x就一定为1或者2，为1的时候上一次就一定为0//为2的时候上一次就一定为1
?? ??? ?dp[index][2] = dp[index - 2][1];
?? ?}
?? ?ans = dp[n][0] + dp[n][1] + dp[n][2];//三个状态相加
?? ?cout << ans;
?? ?return 0;
}
这里有几个问题：
1.我们为什么是Index = 2； index <= n；index++？
答：因为我们知道index = 0或者1的时候x一定为0，这样的话状态是清楚的，子问题是被解决的，问题是发散出去的。
但是如果我们写index = n; index >=0; index--的话，那么最后一个状态我们的子问题是为止的，状态为止，子问题无法被解决，所以是错误的。
总结
一维dp需要思维，二维dp的第二个参数是记录状态的，是限制条件。很难从暴力递归到动态规划。