# 动态规划

动态规划（英语：Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

动态规划问题满足三大重要性质

**最优子结构性质**：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

**子问题重叠性质**：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

**无后效性**：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

## 如何使用
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.

根据题意，首先写出递归版（暴力搜索）的代码
```java
public static int rob(int[] nums,int i){
    if(i<0){
        return 0;
    }
    return Math.max(nums+rob2(nums,i-2),rob2(nums,i-1));
}
```
时间复杂度O(2^N)
暴力搜索中存在太多的冗余（重复计算）过程，所以可以进行记忆化搜索
```python
def rob(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    self.result = [-1]*len(nums)
    return self.slove(len(nums)-1,nums)
        
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];
}
```

我来占层楼啊