動態(tài)規(guī)劃-最小硬幣
- 數(shù)值最少由多少個硬幣組成
public static int minCoins(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return -1;
}
int n = arr.length;
int max = Integer.MAX_VALUE;
int[][] dp = new int[n][aim + 1];
for (int j = 1; j <= aim; j++) {
dp[0][j] = max;
if (j - arr[0] >= 0 && dp[0][j - arr[0]] != max) {
dp[0][j] = dp[0][j - arr[0]] + 1;
}
}
int left = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j <= aim; j++) {
left = max;
if (j - arr[i] >= 0 && dp[i][j - arr[i]] != max) {
left = dp[i][j - arr[i]] + 1;
}
dp[i][j] = Math.min(left, dp[i - 1][j]);
}
}
return dp[n - 1][aim] != max ? dp[n - 1][aim] : -1;
}
字符串
- lloo 去掉 o 成 llo
- AABBCC 去掉 B 成 AABCC
字符串
最少獎品
- 編程比賽成員圍成一個圈，分?jǐn)?shù)高的人要比兩邊分?jǐn)?shù)低的人獲得的獎品更多
左程云編程的分糖果問題
一分二-繩子問題
- N條繩子尤蒿，要求裁剪出M條長度想等的子繩子出來，秋裁剪的繩子長度最長k是多少
設(shè)最長長度為x,得數(shù)學(xué)公式為：
L1/X + L2/X + L3/X + L4/X + ..... + LN/X <= K
酷狗筆試
- 將一個數(shù)組拆分成兩個和相等的數(shù)組栗竖，并且兩個數(shù)組都排序猫胁。
