338. 比特位计数
//枚举的话 nlogn的
//n 的话 ：
//用之前计算的结果
//f[n]: f[n/2]算过了
//f[n] = f[n/2] + 1(奇数时候加一)
class Solution {
public int[] countBits(int num) {
if (num == 0)
return null;
int[] dp = new int[num + 1];
dp[0] = 0;
for(int i = 1; i <= num; i++){
dp[i] = dp[i>>1] + (i & 1);//如果i是奇数时候， 加上1
}
return dp;
}
}
322. 零钱
class Solution {
public int coinChange(int[] coins, int amount) {
int [] f = new int[amount + 1];
f[0] = 0;
for(int i = 1; i <= amount; i++){
int cost = Integer.MAX_VALUE; //此目标值下的 硬币个数 //cost用于存储每个目标值的dp[i]
for(int j = 0; j < coins.length; j++){
if(i - coins[j] >= 0){ //如果能填这个硬币
if(f[i-coins[j]] != Integer.MAX_VALUE) // 如果上一个存在
cost = Math.min(cost, f[i - coins[j]] + 1);
}
}
f[i] = cost; //赋值
}
return f[amount] == Integer.MAX_VALUE? -1 : f[amount];
}
}
221. 最大正方形
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length <= 0 ||matrix[0] == null || matrix[0].length <= 0)
return 0;
int n = matrix.length, m = matrix[0].length;
int[][] dp = new int[n][m]; //dp中存放最大边长
int res = 0;
//dp[0][0] = Integer.valueOf(matrix[0][0]);
for (int i = 0; i < n ; i++){
for (int j = 0; j < m; j++){
if (matrix[i][j] == '0')
dp[i][j] = 0;
else{
dp[i][j] = 1;
if (i >= 1 && j >= 1)
dp[i][j] += Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])); //边长取最小+1
res = Math.max(res, dp[i][j]);
}
}
}
return res * res;
}
}
91. 解码方法
// f[i]: 截至第i位有多少
// f[i] = 1. f[i] 可否表示(>0) ：f[i] += f[i -1]
//2. f[i]和f[i-1]可否表示(10-26) : f[i] += f[i -2]
class Solution {
public int numDecodings(String s) {
if (s == null || s.length() <= 0)
return 0;
int len = s.length();
int[] dp = new int[len + 1];
s = ' ' + s;
dp[0] = 1; //第一个位置的前面，初始化位一
for (int i = 1; i <= len; i++){
dp[i] = 0;
if (s.charAt(i) != '0')
dp[i] += dp[i - 1]; //自己单独一位
if(i > 1){
int t = (s.charAt(i - 1) - '0') *10 + (s.charAt(i) - '0'); //得数字
if (t >= 10 && t <= 26)
dp[i] += dp[i - 2];
}
}
return dp[len];
}
}
263. 丑数
class Solution {
public int nthUglyNumber(int n) {
ArrayList<Integer> q = new ArrayList<Integer>();
q.add(1);
int i = 0, j = 0, k = 0;
while (--n >0){
int t = Math.min(q.get(i)*2,Math.min(q.get(j)*3, q.get(k)*5));
q.add(t);
if (q.get(i) * 2 == t) i++;
if (q.get(j) * 3 == t) j++;
if (q.get(k) * 5 == t) k++;
}
return q.get(q.size() - 1);
}
}
115. 不同的子序列
class Solution {
//相同： f[i][j] = f[i -1][j - 1] + (不用)f[i -1][j];
//不相同：f[i][j] = f[i -1][j];
public int numDistinct(String s, String t) {
if (s == null || t == null)
return 0;
int n = s.length(), m = t.length();
int[][] dp = new int[n+1][m+1];
for (int i = 0; i <= n; i++) //初始化边界
dp[i][0] = 1; //全不匹配
for(int i = 1; i<=n; i++){
for (int j = 1; j <=m; j++){
dp[i][j] = dp[i - 1][j];
if (s.charAt(i - 1) == t.charAt(j -1))
dp[i][j] += dp[i-1][j-1];
}
}
return dp[n][m];
}
}
