ORID40

今天写了一道题，发现这个式子很有意思

int[] count = new int[26];
++count[s.charAt(Index) - 'A'];

这一句到底在做什么呢？ 就是count[] 这个array里面就代表26个字母的出现频率（0-25），而你在s.charAt(index) 这就会看到当前index指向的字母，用它减去'A'其实就得到了ASCII code的值，只不过把它们缩小到了0-25的范围，好让你更好的放进count这个array里面。左边两个++就是计数了。

dynamic programming 分四步
第一步，确定状态。也就是找到最后找到答案之前应该可以由什么结果得出，子问题
第二步，方程转化。初始。initialization
第三步，输出条件和边界情况
第四步，计算顺序

解题报告 [322]coin change

算法

用什么算法？
dynamic programming。这题让你算出能够凑出amount值所用的最少硬币。那么，给你硬币的数组 coin[], 这个时候从最后的值往前想就只有coin.length种可能。 而每一个可能又是基于上一个最少的组合。所以大问题就被拆成了小问题。
子问题
动态规划要注意的就是initialize，还有state。这里的initialize就是0，因为你不用任何硬币去凑出0这个值。state就是你当前的值能够用最少硬币凑出的值。
所以你要判断用coin[]里面每一个值所需的最少数目。比如amount[1], 你coin 里面只有[2,3,5] ，那么你是凑不出来的，所以你进入for循环一开始就要设置成Integer.MAX_VALUE，这样在进入判断条件的时候，你只要替换掉这个最大值就可以了。如果没达到你的要求（也就是凑不出来），那么这个数就是最大值。达到了就用最小数替换掉。
所以这个判断条件是关键

代码实现

public int minCombination(int[] coins, int amount) {
        int[] dp = new int[amount + 1]; //因为是0-amount，所以用amount + 1;
        dp[0] = 0; //initialize
        for (int i = 1; i <= amount; i++) {
          dp[i] = Integer.MAX_VALUE; // 像之前解释的，达到要求在替换，达不到就代表凑不出当前这个值
          for (int j : coins) {
              if (i - j >= 0 && dp[i - j] != Integer.MAX_VALUE && dp[i - j] + 1 < dp[i] {    
//解释一下，如果i - j < 0，那么就代表当前的coin数值已经大于你要凑出的数字了，没有意义，所以不要更新最小能凑出的数。
//如果当前要凑出的值(也就是i) 减去当前硬币的值是Integer.MAX_VALUE，那么就代表你凑不出这个数。因为之前已经算过了。最后一个判断条件就是在不断更新最小可能的硬币组合） 
                  dp[i] = dp[i - j] + 1;
              }
          }
        }
      if (dp[amount] == Integer.MAX_VALUE) {
        return -1;
      } else {
        return dp[amount];
      }
}