【每日算法Day 57】DP强化理解1

动态规划问题一般是求最值，例如最长递增子序列、最小编辑距离等等。所以其核心问题是穷举，不过动态规划穷举地问题存在重叠子问题与最优子结构，这时需要用备忘录来优化穷举过程。同时，找出正确的状态转移方程才能正确地穷举。

通常我们拿到一个可能使用动态规划解决地问题时，依次要思考以下几点：

base case 是什么？问题在某一阶段的状态是什么？问题在状态间转移时有哪些选择？

想清楚这三点后就可以给出dp数组的定义与状态转移方程了。其实状态转移方程可以直接对应递归的暴力解法，其中的重叠子问题可以使用备忘录的方式来优化。而最优子结构问题则对应着状态转移时要作出的选择。

LeetCode 322. 零钱兑换 (opens new window)

题目描述

给定不同面额的硬币 coins[] 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

解题思路

该题的边界case是所有硬币都不选，这时硬币个数为0，总金额为0。问题的状态是：在总金额为T时最少选取了硬币i个。问题在状态间转移的选择就是对于可选的不同面额的硬币选择其中一个(i++)，再更新对应总金额处的最小硬币数量。

public int coinChange(int[] coins, int amount) {
    if (coins==null||coins.length==0||amount<0) return -1;
    if(amount==0) return 0;
    int[] dp = new int[amount+1];
    Arrays.fill(dp,-1);
    //初始化边界情况，只选择一枚硬币
    for (int coin : coins) {
        if(coin<=amount){
            dp[coin]=1;
        }
    }

    for (int i = 1; i <=amount ; i++) {
        //如果当前金额可以达到
        if (dp[i]!=-1){
            //选择一枚硬币
            for (int coin : coins) {
                //如果下标不越界的话则更新对应总金额处的最小硬币数量
                //注意这里不能用i+coin<=amount来判断，因为i+coin可能溢出为负数
                if (amount-coin>=i) {
                    dp[i + coin] = dp[i + coin] == -1 ? dp[i] + 1 : Math.min(dp[i + coin], dp[i] + 1);
                }
            }
        }
    }
    return dp[amount];
}