## 如何使用
1 设计暴力算法，找到冗余
2 设计并存储状态(一维，二维，三维数组，甚至用Map)
3 递归式(状态转移方程)
4 自底向上计算最优解(编程方式)
## 例题1
### House Robber
>You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
>
>Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
>
>Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.
def slove(self,i,nums):
if i < 0:
return 0
if self.result >= 0:
return self.result
self.result = max(nums+self.slove(i-2,nums), self.slove(i-1,nums))
return self.result
```
记忆化搜索基本达到了动态规划的要求，但是时间复杂度从表面很难估算出来，当数组长度过大的时候，不好处理
可以确定本地的状态转移方程：F(n) = Max( F(i-2)+nums, F(i-1) )
如果将记忆化搜索改为递推式的话，一定注意边界条件的处理
```java
public int rob(int[] nums) {
if(nums.length == 0){
return 0;
}
if(nums.length == 1){
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i =2 ;i < nums.length;i++){
dp = Math.max(nums+dp[i-2],dp[i-1]);
}
return dp[nums.length-1];
}
```
## 例题2
###
> You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
>
>Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
>
>Example 2:
coins = [2], amount = 3
return -1.
>
>Note:
You may assume that you have an infinite number of each kind of coin.
>
>Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
```java
public static int search(int[] coins,int i,int amount){
if(amount == 0){
return 0;
}
if(amount < 0){
return Integer.MAX_VALUE>>1;
}
if( i >= coins.length){
return Integer.MAX_VALUE>>1;
}
return Math.min(search(coins,i,amount-coins)+1,search(coins,i+1,amount));
}
public static int search2(int[] coins,int amount){
int[][] dp = new int[coins.length+1][amount+1];
for(int j=0;j<=coins.length;j++) {
for (int i = 0; i <= amount; i++) {
dp[j] = amount + 1;
}
dp[j][0] = 0;
}
for(int i = 1;i<=coins.length;i++){
for(int j=0;j<=amount;j++){
if(coins[i-1]<=j){
dp[j] = Math.min(dp[j-coins[i-1]]+1,dp[i-1][j]);
}else{
dp[j] = dp[i-1][j];
}
}
}
return dp[coins.length][amount] == amount+1? -1 : dp[coins.length][amount];
}
```
其实对于动态规划的大多数题目，如果二维的数组来存储状态的话，通常第一维度都是表示行的，如果第n行的数据通常由n+1行或者n-1行直接决定，那么可以利用**滚动数组**直接降低空间复杂度，代码可以改为如下：
```java
public int coinChange(int[] coins, int amount) {
int[][] dp = new int[2][amount+1];
for(int j=0;j<=1;j++) {
for (int i = 0; i <= amount; i++) {
dp[j] = amount + 1;
}
dp[j][0] = 0;
}
for(int i = 1;i<=coins.length;i++){
for(int j=0;j<=amount;j++){
if(coins[i-1]<=j){
dp[i%2][j] = Math.min(dp[i%2][j-coins[i-1]]+1,dp[(i-1)%2][j]);
}else{
dp[i%2][j] = dp[(i-1)%2][j];
}
}
}
return dp[coins.length%2][amount] == amount+1? -1 : dp[coins.length%2][amount];
}
```