硬币变换算法 - 具有一维阵列的DP

2 回答

• 0

  好吧，我自己想通了！

  这可以使用归纳法轻松证明 . 让table [k]表示可以给出总共k的变化方式 . 现在算法由两个循环组成，一个由i控制并迭代通过包含所有不同硬币的数组，另一个是j控制循环，对于给定的i，它更新数组表中元素的所有值 . 现在考虑一个固定的i，我们计算了从1到n的所有值的变化方式的数量，这些值存储在表[1]到表[n]的表中 . 当i控制循环迭代i 1时，任意j的表[j]中的值增加表[jS [i 1]]，这只是我们可以使用至少一个值为S的硬币创建j的方式[i 1]（存储硬币值的数组） . 因此，表[j]中的总值等于我们可以使用值为S [1]的硬币创建变更的方式.... S [i]（之前已经存储过）和值表[jS [i] 1]] . 这与递归算法中使用的问题的最优子结构相同 .

  回复于 2024-04-25T16:33:03+08:00
• 1

  int arr[size];
  memset(arr,0,sizeof(size));
  int n;
  cin>>n;
  int sum;
  cin>>sum;
  int a[size];
  fi(i,n)
  cin>>a[i];
  arr[0]=1;
  fi(i,n)
  for(int j=arr[i]; j<=n; j++)
      a[j]+=a[j-arr[i]];
  cout<<arr[n];
  

  数组 arr 初始化为0，以便表明 i 之和的方式的数量为零（即未初始化） . 但是，可以表示0之和的方式的数量是1（零路） . 此外，我们拿出每个硬币并从硬币面额开始初始化阵列中的每个位置 . a[j]+=a[j-arr[i]] 意味着我们基本上增加了以前所需数量的方式表示和 j 的可能方式（ j-arr[i] ） . 最后，我们输出 a[n]

  回复于 2024-04-25T16:33:03+08:00