343. 整数拆分

image.png

递归+备忘录

  1. class Solution {
  2.     int[] memo = new int[60];
  3.     public int integerBreak(int n) {
  4.         return dfs(n);
  5.     }
  7.     int dfs(int n) {
  8.         if (n == 2) return 1;
  9.         if (memo[n] != 0) return memo[n];
  10.         int res = 0;
  11.         for (int i = 1; i < n - 1; i++) {
  12.            //  res = Math.max(res, dfs(i) * (n - i));
  13.             res = Math.max(res, dfs(n - i) * i);
  14.             res = Math.max(res, (n - i) * i);
  15.         }
  16.         memo[n] = res;
  17.         return res;
  18.     }
  19. }

动态规划

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        if (n == 2) return 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
            for (int j = 1; j <= i ; j++) {
                dp[i] = Math.max(dp[i - j] * j, dp[i]);
                dp[i] = Math.max((i - j) * j, dp[i]);
            }
        return dp[n];
    }
}

279. 完全平方数

image.png

递归

class Solution {
    public int numSquares(int n) {
        return dfs(n);
    }

    int dfs(int n) {
        if (n == 1) return 1;
        int res = n;
        for (int i = 1; i * i <= n; i++) {
            res = Math.min(res, dfs(n - i * i) + 1);
        }
        return res;
    }
}

备忘录

class Solution {
    int[] memo = new int[10010];
    public int numSquares(int n) {
        return dfs(n);
    }

    int dfs(int n) {
        if (n == 1) return 1;
        if (memo[n] != 0) return memo[n];
        int res = n;
        for (int i = 1; i * i <= n; i++) {
            res = Math.min(res, dfs(n - i * i) + 1);
        }
        memo[n] = res;
        return res;
    }
}

动态规划

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

91. 解码方法

image.png

// 未通过  "2101"测试用例输出3
class Solution {
    int[] memo = new int[101];
    public int numDecodings(String s) {
        Arrays.fill(memo, -1);
        if (s.charAt(0) == '0') return 0;
        return dfs(s, 0);
    }

    int dfs(String s, int start) {
        // 当前位置为0，剪枝
        if (start != s.length() && s.charAt(start) == '0') return 0;
        // 找到一个解码方法
        if (start == s.length()) return 1;
        // 已经找到过一次
        if (memo[start] != -1) return memo[start];
        // 下个位置为0， 只能用两位去解码
        if (start + 1 < s.length() && s.charAt(start + 1) == '0')
            return dfs(s, start + 2);
        // 可以使用两种方式解码
        int num1 = dfs(s, start + 1), num2 = 0;
        if (start + 1 < s.length()) {
            // 尝试使用两个数解码 考虑是否<=26
            int n1 =  s.charAt(start) - '0', n2 = s.charAt(start + 1) - '0';
            if (n1 * 10 + n2 <= 26) {
                num2 = dfs(s, start + 2);
            } 
        }
        memo[start] = num1 + num2;
        return num1 + num2;
    }
}