算法#1:动态规划中的排列与组合问题

最近在刷力扣，遇到了几道有意思的动态规划问题，记录下我的思考题目链接🔗: https://leetcode.cn/problems/coin-change-ii/description/ https://leetcode.cn/problems/coin-change/description/ https://leetcode.cn/problems/climbing-stairs/description/ 首先看两端不同的代码：

//第一种
int dp[amount+1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int j = 1; j <= amount; j++){
    for (int coin : coins){
        if (j < coin) continue;
        dp[j] += dp[j-coin];
    }
}
return dp[amount];
//第二种
int dp[amount+1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int coin : coins){
    for (int j = 1; j <= amount; j++){
        if (j < coin) continue;
        dp[j] += dp[j-coin];
    }
}
return dp[amount];

这两份代码只是for嵌套的顺序不同，但是分别是求解决方案的排序数和组合数，下面我将从动态规划的子问题划分和代码实现上的区别说明这两段代码的区别。

对于子问题的划分

动态规划可以大致被分为

定义子问题
确定状态表示
通过划分集合，从集合的角度思考状态转移的方程
确定边界问题

在这两段代码里，第一种的子问题被确定为：对于金额i来说我们最后一个选择第j个硬币的方案，这种划分方法实际上是会将[1,2] [2,1]看成是两种不一样的方法，因为从划分的角度来看1，2是两种不同的”第j个硬币的方案”，也就是说，这种方法求的是排列数。但是在第二种方法中，子问题被划分为前i枚硬币组合出j个金额的方案数，从这个角度来讲上述中的[1,2] [2,1]在这一子问题中是一种方案，因为他们都是前两个硬币中凑出金额为3的解决方案(假设硬币面值为1，2的硬币是集合中的前两个) 这是从子问题的角度来看，两种写法的子问题是不同的以及这种特性使得两种写法的子集具有有序性与无序性

代码实现分析

这部分是我个人的理解。第一种写法，两层for循环外面是枚举金额数，里层枚举每个硬币，因此在代码运行时就会把先遍历硬币的先后顺序不同的方案而看成不同的方案，因此具有有序性。第二种写法，外层遍历的是硬币，里层是金额数，这保证了硬币的使用是有顺序的，也就是说，先使用第i个硬币，再使用第i+1个硬币，你可以抽象的理解为先将第i个硬币在能放的金额数里都放完再放下一个硬币，所以不是集合本身失去了有序性，而是这种写法使得硬币使用的顺序是有序的，所以结果是组合数

一些奇怪的联想🤔

这种有序和无序性的集合遍历之前是在dfs中遇到过，具体代码如下:

void dfs(
    int idx, int x,
    int total) {
  //避免重复选取相同元素不同排序的结果
  if (idx > k) {
    if (isPrime(total))
      ans++;
    return;
  }
  for (int i = x; i <= n; i++) {
    if (!used[i]) {
      used[i] = 1;
      dfs(idx + 1, i + 1, total + num[i]);
      used[i] = 0;
    }
  }
}

这种写法同样也是防止dfs在枚举子集的过程中出现[1,2][2,1]是不同情况的错误，和今天的算法有异曲同工之妙，都是通过人为的使得枚举具有固定的先后顺序防止重复枚举相同元素的子集