# 1, 1143 Longest common subsequence

Give you an integer array of coins to represent coins of different denominations; And an integer amount, representing the total amount.

Calculate and return the minimum number of coins required to make up the total amount. If no combination of coins can make up the total amount, return - 1.

You can think that the number of coins of each kind is unlimited.

Source: LeetCode

I first thought about decreasing from the maximum face value. As a result, I found that this approach could not find a combination that met the conditions, and many elements would be missed. I was just looking for the minimum number, but I missed the combination that might be enough. Greed alone is not enough

```class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
//First spell the one with a large face value
int n = coins.size(), cnt = 0;
sort(coins.begin(), coins.end());
for (int i = n - 1; i >= 0; --i){
while(amount >= coins[i]){
amount -= coins[i];
++cnt;
}
}
if (amount == 0){
return cnt;
}
else {
return -1;
}
}
};
```

# 2, 12 Integer to Roman numeral

Roman numerals contain the following seven characters: I, V, X, L, C, D and M.

Character value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, the Roman numeral 2 is written as II, which is two parallel ones. 12 is written as XII, which is X + II. 27 is written as XXVII, which is XX + V + II.

Usually, the small Roman numerals are to the right of the large ones. But there are also special cases. For example, 4 is not written as IIII, but IV. The number 1 is on the left of the number 5, and the number represented is equal to the value 4 obtained by subtracting the decimal 1 from the large number 5. Similarly, the number 9 is represented as IX. This special rule applies only to the following six cases:

I can be placed to the left of V (5) and X (10) to represent 4 and 9.
X can be placed to the left of L (50) and C (100) to represent 40 and 90.
C can be placed to the left of D (500) and M (1000) to represent 400 and 900.
Give you an integer and convert it to Roman numerals.

Source: LeetCode

```class Solution {
public:
string intToRoman(int num) {
//Check from the high position. Special treatment is required if it is 4 and 9
const pair<int, string> Roman[] = {
{1000, "M"},
{900, "CM"},
{500, "D"},
{400, "CD"},
{100, "C"},
{90, "XC"},
{50, "L"},
{40, "XL"},
{10, "X"},
{9, "IX"},
{5, "V"},
{4, "IV"},
{1, "I"},
};
string ans;
for (auto &[value, str] : Roman){
while (num >= value){
num -= value;
ans += str;
}
if (num == 0){
break;
}
}
return ans;
}
};
```

# 3, 13 Roman numeral to integer

```class Solution {
public:
unordered_map<char, int>  Roman = {
{'M', 1000},
{'D', 500},
{'C', 100},
{'L', 50},
{'X', 10},
{'V', 5},
{'I', 1},
};
int romanToInt(string s) {
//The key is to deal with 4 and 9
int n = s.size(), ans = 0;
for (int i = 0; i < n; ++i){
int value = Roman[s[i]];
if (i < n - 1 && value < Roman[s[i + 1]]){//In case of 4 and 9
ans -= value;
}
else {
ans += value;
}
}
return ans;
}
};

```

Keywords: Algorithm leetcode greedy algorithm

Added by heepofajeep on Sun, 13 Feb 2022 04:03:44 +0200