区间DP:lintcode-1884拿走瓶子
lintcode 好像比 leetcode 的题难一些，
1884 · 拿走瓶子
描述
有一排有编号的瓶子，现在你需要将这些瓶子全部拿走。
你每次只可以拿走连续的若干个瓶子，并且需要保证瓶子的编号是一个“回文串”。
回文串指的是正着和反着读都一样的串，例如“121”和“4664”。
返回拿走所有瓶子所需要的最少次数。
区间DP，没想出来。
public class Solution {
/**
* @param arr: the array of bottles
* @return: the minimum number of times you can take all the bottles
*/
public int takeAwayTheBottle(int[] arr) {
// Write your code here.
int n = arr.length;
int[][] dp = new int[n][n];
// 初始化为最大值
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
dp[i][j] = 1001;
}
}
for(int i=0;i<n;i++) {
dp[i][i] = 1;
}
for(int i=1;i<n;i++) {
if(arr[i-1]==arr[i]) {
dp[i-1][i] = 1;
} else {
dp[i-1][i] = 2;
}
}
for(int l=2;l<=n;l++) {
for(int i=0;i+l<n;i++) {
int j = i+l;
if(arr[i]==arr[j]) {
dp[i][j] = dp[i+1][j-1];
} else {
for (int k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
}
return dp[0][arr.length-1];
}
}
1882 · 公平索引
前缀和，配不上它标的中等题。也是今天好不容易碰到的会的一道题了。
1707 · 骑士拨号器
本来写的是递归，但是大数会overflow。
改成了迭代。
public class Solution {
/**
* @param n: N
* @return: return the number of distinct numbers can you dial in this manner mod 1e9+7
*/
Map<Integer,Integer> cache = new HashMap<>();
public int knightDialer(int n) {
Map<Integer,List<Integer>> map = new HashMap<>();
for(int i=0;i<=9;i++) {
map.put(i,new ArrayList<>());
}
map.get(0).add(4);
map.get(0).add(6);
map.get(1).add(6);
map.get(1).add(8);
map.get(2).add(7);
map.get(2).add(9);
map.get(3).add(4);
map.get(3).add(8);
map.get(4).add(9);
map.get(4).add(3);
map.get(4).add(0);
map.get(6).add(0);
map.get(6).add(7);
map.get(6).add(1);
map.get(7).add(2);
map.get(7).add(6);
map.get(8).add(1);
map.get(8).add(3);
map.get(9).add(4);
map.get(9).add(2);
int[] count = new int[10];
Arrays.fill(count,1);
for(int k=2;k<=n;k++) {
int[] next = new int[10];
for(int i=0;i<=9;i++) {
for(int j=0;j<map.get(i).size();j++) {
next[i] += count[map.get(i).get(j)];
next[i] %= 1000000007;
}
}
for(int i=0;i<=9;i++) {
count[i] = next[i];
}
}
int result = 0;
for(int i=0;i<=9;i++) {
result += count[i];
result %= 1000000007;
}
return result;
}
}
1821 · 最小删除以获得正确格式的字符串
转换为AABB。。的最长长度，遍历查找当前字母前面的A有几个，后面的B有几个。
public class Solution {
/**
* @param s: the string
* @return: Min Deletions To Obtain String in Right Format
*/
public int minDeletionsToObtainStringInRightFormat(String s) {
int[] countA = new int[s.length()];
int[] countB = new int[s.length()];
int a = 0;
int b = 0;
for(int i=0;i<s.length();i++) {
if(s.charAt(i)=='A') {
a++;
}
countA[i] = a;
}
for(int i=s.length()-1;i>=0;i--) {
if(s.charAt(i)=='B') {
b++;
}
countB[i] = b;
}
int maxLen = 0;
for(int i=0;i<s.length();i++) {
maxLen = Math.max(maxLen,countA[i]+countB[i]);
}
return s.length()-maxLen;
}
}