343. Integer Break (Medim)

题目描述
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
思路
当i≥2 时，假设对正整数 i 拆分出的第一个正整数是 j（1≤j将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]。

  1. class Solution {
  2.     public int integerBreak(int n) {
  3.         int[] dp = new int[n+1];
  4.         dp[1] = 1;
  5.         dp[2] = 1;
  6.         for(int i=3; i<=n; i++){
  7.             for(int j = 2; j<i; j++){
  8.                 dp[i] =Math.max( Math.max(j*(i-j),j*dp[i-j]), dp[i]);
  9.             }
  10.         }
  11.         return dp[n];
  12.     }
  13. }

其他优化见leetcode题解

279. Perfect Squares(Medium)

题目描述
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
思路
同上，双重循环遍历

  1. class Solution {
  2.     public int numSquares(int n) {
  3.         List<Integer> list = new ArrayList<>();
  4.         for(int i=1; i<=n/2; i++){
  5.             list.add(i*i);
  6.         }
  7.         int[] dp = new int[n+1];
  8.         dp[1] = 1;
  9.         for(int i=2; i<n+1; i++){
  10.             int min = Integer.MAX_VALUE;
  11.             for(int sq: list){
  12.                 if(sq>i){
  13.                     break;
  14.                 }
  15.                 min = Math.min(min,dp[i-sq]+1);
  16.             }
  17.             dp[i] = min;
  18.         }
  19.         return dp[n];
  20.     }
  21. }

91. Decode Ways (Medium)

题目描述
一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
题目数据保证答案肯定是一个 32 位的整数。
示例
输入：s = “226”
输出：3
解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
思路
若c[i]与c[i-1]构成的数小于等于26，dp[i] = dp[i-1] + dp[i-2], 否则，dp[i]=dp[i-1]. 零需要单独考虑！

  1. class Solution {
  2.     public int numDecodings(String s) {
  3.         int len = s.length();
  4.         int[] dp = new int[len+1];
  5.         dp[0] = 1;
  6.         dp[1] = s.charAt(0)=='0'?0:1;
  7.         int pre = s.charAt(0) - '0';
  8.         for(int i=2; i<len+1; i++){
  9.             int cur = s.charAt(i-1)-'0';
  10.             if(cur!=0){
  11.                 dp[i] = dp[i]+dp[i-1];
  12.             }
  13.             if(pre==0){
  14.                 pre = cur;
  15.                 continue;
  16.             }
  17.             if(pre*10+cur<=26){
  18.                 dp[i] += dp[i-2];
  19.             }
  20.             pre = cur;
  21.         }
  22.         return dp[len];
  23.     }
  24. }

结果
image.png