C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++でのコインチェンジ2

異なる金種のコインと合計金額があるとします。その量を構成する組み合わせの数を計算するモジュールを作成する必要があります。コインの種類ごとに無限の数があると想定できます。したがって、金額が5で、コインが[1、2、5]の場合、4つの組み合わせがあります。 （1 + 1 + 1 + 1 + 1）、（1 + 1 + 1 + 2）、（1 + 2 + 2）、（5）

これを解決するには、次の手順に従います-

  • サイズ量+1の配列dpを1つ作成します
  • dp [0]：=1
  • n：=コイン配列のサイズ
  • 0からn–1の範囲のiの場合
    • 範囲コインのjの場合[i]から金額まで
      • dp [j]：=dp [j –コイン[i]]
  • return dp [amount]
例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int change(int amount, vector<int>& coins) {
      vector <int> dp(amount + 1);
      dp[0] = 1;
      int n = coins.size();
      for(int i = 0; i < n; i++){
         for(int j = coins[i]; j <= amount; j++){
            dp[j] += dp[j - coins[i]];
         }
      }
      return dp[amount];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,5};
   cout << (ob.change(5, v));
}
入力 
5
[1,2,5]

出力

4

  1. C ++を使用してOpenCVのコントラストを変更するにはどうすればよいですか？

    明るさやコントラストの変更は、画像処理で頻繁に編集される効果です。ここでは、画像のコントラストを変更する方法を学習します。コントラストは、画像の鮮明さを制御します。コントラストが高いほど画像が鮮明になり、コントラストが低くなると画像が窒息します。 コントラストを変更すると、ピクセルの重みが大きくなります。コントラストが高いほど、画像は鮮明になります。コントラストを変更するには、ピクセル値に定数を掛けます。たとえば、画像のすべてのピクセル値に2を掛けると、ピクセルの値が2倍になり、画像がより鮮明になります。 次のプログラムは、OpenCVで画像のコントラストを変更する方法を示しています。 例

  2. コイン交換のためのPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 − N枚のコインが与えられ、Sに各値が無限に供給されるように、それらのコインを変更したいと考えています。順序に関係なく、変更できる方法がいくつあるかを表示する必要があります。 動的計画法の概念を使用して問題ステートメントを解決し、時間の複雑さを軽減します。 次に、以下の実装のソリューションを見てみましょう- 例 # dynamic approach def count(S, m, n):    # base case    table = [[0 for x in