#
##
##
-
```java
int[] array = {15, 85, 55, 99, 26}
```
###
-
```java
//
private static class Node {
//
E item;
//
Node next;
//
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
//
private static class Node {
//
E item;
//
Node next;
Node(E element, Node next) {
this.item = element;
this.next = next;
}
}
```
> next head head prev
>
> head
###
queue ********
-
###
###
****
- root
- C P P.value >= C.value
- C P P.value , .
####
```java
/**
*
*
* F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13
* 0 1 1 2 3 5 8 13 21 34 55 89 144 233
* @param n
* @return
*/
public int fibonacci(int n) {
if (n == 0) {
return n;
}
if (n == 1) {
return n;
}
int a = 0;
int b = 1;
for (int i = 2; i = item0.weight) {
dp[j] = item0.value;
}
}
for (int i = 1; i < items.length; i++) {
for (int j = capacity; j > 0; j--) {
//
if (j >= items[i].weight) {
dp[j] = Integer.max(dp[j], items[i].value + dp[j - items[i].weight]);
}
}
}
return dp[capacity];
}
/***/
static class Item {
/***/
private int index;
/***/
private String name;
/**(g)*/
private int weight;
/***/
private int value;
public Item(int index, String name, int weight, int value) {
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
}
```
####
`` `01`
- `01`
- ``
```java
/**
*
1. 10g
2. ?
(g) ()
1 2 3 (c)
2 3 4 (s)
3 4 5 (a)
0 1 2 3 4 5 6
1 0 0 c c cc cc ccc
2 0 0 c s s sc ss
3 0 0 c s a a ac
if () {
dp[i][j] = dp[i-1][j]
} else {
// = max(, + )
dp[i][j] = max(dp[i-1][j], item.value + dp[i-1][j-item.weight])
}
*
* @param items
* @param capacity
* @return
*/
public int select(Item[] items, int capacity) {
int [] dp = new int[capacity + 1];
Item item0 = items[0];
// 0
for (int j = 0; j < capacity + 1; j++) {
// 0
if (j >= item0.weight) {
dp[j] = dp[j - item0.weight] + item0.value;
}
}
for (int i = 1; i < items.length; i++) {
for (int j = capacity; j > 0; j--) {
//
if (j >= items[i].weight) {
dp[j] = Integer.max(dp[j], items[i].value + dp[j - items[i].weight]);
}
}
}
return dp[capacity];
}
static class Item {
/***/
private int index;
/***/
private String name;
/**(g)*/
private int weight;
/***/
private int value;
public Item(int index, String name, int weight, int value) {
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
}
```
#### --
```java
/**
0 1 2 3 4 5
1 0 1 11 111 1111 11111
2 0 1 2 21 22 221
5 0 1 2 21 22 1
-
-
- 1
if () {
, +1 1
dp[j] = Integer.min(dp[j], dp[j - coins[i]] + 1);
// dp[i][j] = max(dp[i-1][j], dp[i-1][j-item.weight] + 1)
} else {
dp[i][j] = dp[i-1][j]
}
* @param coins
* @param amount
* @return
*/
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 0Arrays.fill
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int j = coin; j < amount + 1; j++) {
dp[j] = Integer.min(dp[j], dp[j - coin] + 1);
}
}
return dp[amount] < amount ? dp[amount] : -1;
}
```
#### --
```java
/**
0 1 2 3 4 5 -
1 1 1 11 111 1111 11111
2 1 1 11 111 1111 11111
2 21 211 2111
22 221
5 1 1 11 111 1111 11111
2 21 211 2111
22 221
5
i: j:
1 +
eg: 312 dp[i][j] = dp[i-1][j] + dp[i][j-coin]
if () {
dp[i][j] = dp[i-1][j] + dp[i][j-coin]
} else {
dp[i][j] = dp[i-1][j]
}
* @param coins
* @param amount
* @return
*/
public int change(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int j = 1; j < amount + 1; j++) {
if (j >= coins[0]) {
dp[j] = dp[j - coins[0]];
}
}
for (int i = 1; i < coins.length; i++) {
for (int j = 1; j < amount + 1; j++) {
//
if (j >= coins[i]) {
dp[j] = dp[j] + dp[j - coins[i]];
}
}
}
return dp[amount];
}
```
####
```java
/**
.
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30
3m
0 1 2 3 4
1 1 11 111 1111
1 2 3 4
2 1 11 111 1111
2 21 211
22
1 5 6 10
3 1 11 111 1111
2 21 211
3 22
31
... ...
if () {
, +
dp[i][j] = max(dp[i-1][j], + dp[i][j-])
} else {
dp[i][j] = dp[i-1][j]
}
* @param values - ()
* 0 1 2 3 4 5 6 7 8 9 10
* 0 1 5 8 9 10 17 17 20 24 30
* @param n
* @return
*/
public int cut(int[] values, int n) {
int[] dp = new int[n + 1];
for (int i = 1; i < values.length; i++) {
for (int j = 1; j < n + 1; j++) {
if (j >= i) {
dp[j] = Integer.max(dp[j], values[i] + dp[j - i]);
}
}
}
return dp[n];
}
```
####
```java
/**
abcdeoma opcdeima 3
b c d e i m a
c 0 1 0 0 0 0 0
d 0 0 2 0 0 0 0
e 0 0 0 3 0 0 0
o 0 0 0 0 0 0 0
m 0 0 0 0 0 1 0
a 0 0 0 0 0 0 2
if () {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = 0
}
* @param a A
* @param b B
* @return
*/
public int lcs(String a, String b) {
int[][] dp = new int[b.length()][a.length()];
int max = 0;
for (int i = 0; i < b.length(); i++) {
for (int j = 0; j < a.length(); j++) {
if (a.charAt(j) == b.charAt(i)) {
// 0000dp[i - 1][j - 1]
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
max = Integer.max(max, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return max;
}
```
####