划分型动态规划:
513. Perfect Squares
- public class Solution {
- /**
- * @param n: a positive integer
- * @return: An integer
- */
- public int numSquares(int n) {
- // write your code here
- if (n==0){
- return 0;
- }
- int[] f = new int[n+1];
- for(int i=1;i<=n;i++){
- f[i] = Integer.MAX_VALUE;
- for(int j=1;j*j<=i;j++){
- f[i]= Math.min(f[i-j*j]+1,f[i]);
- }
- }
- return f[n];
- }
- }
- View Code
- 108. Palindrome Partitioning
- public class Solution {
- /**
- * @param s: A string
- * @return: An integer
- */
- public int minCut(String ss) {
- // write your code here
- if(ss==null || ss.length()==0){
- return 0;
- }
- char[] s = ss.toCharArray();
- int[] f = new int[s.length+1];
- boolean[][] isPalin = calcPalin(s);
- for(int i=1;i<=s.length;i++){
- f[i]= Integer.MAX_VALUE;
- for(int j=0;j<i;++j){
- if(isPalin[j][i-1]){
- f[i]= Math.min(f[i],f[j] +1);
- }
- }
- }
- return f[s.length]-1;
- }
- private boolean[][] calcPalin(char[] s){
- int n = s.length;
- boolean [][] isPalin = new boolean[n][n];
- for(int mid =0;mid<n;mid++){
- int i = mid;
- int j = mid;
- while(i>=0 && j<n && s[i]==s[j]){
- isPalin[i][j]= true;
- --i;
- ++j;
- }
- i= mid;
- j= mid+1;
- while(i>=0 && j<n && s[i]==s[j]){
- isPalin[i][j]= true;
- --i;
- ++j;
- }
- }
- return isPalin;
- }
- }
- View Code
博弈型动态规划:
394. Coins in a Line
- public class Solution {
- /**
- * @param n: An integer
- * @return: A boolean which equals to true if the first player will win
- */
- public boolean firstWillWin(int n) {
- // write your code here
- if(n==0) return false;
- if(n==2 || n==1) return true;
- boolean[] f = new boolean[n+1];
- f[1]=f[2]=true;
- f[0]=false;
- for(int i=2;i<=n;i++){
- f[i] = !f[i-1]||!f[i-2];
- }
- return f[n];
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-3042715.html