动态规划笔记

动态规划特点

1. 计数
   -有多少种方式从一点到一点
   -有多少种方法选出k个数使得和是Sum
2. 求最大最小值
   -从左上角走到右下角路径的最大数字和
   -最长上升子序列长度
3. 求存在性
   -取石子游戏，先手是否必胜
   -能不能选出k个数使得和是Sum

先贴代码：

package LinkCode;

public class Solution {
    /**
     * @param A: a list of integer
     * @param M: a total M of money M
     * @return: the fewest number of A that you need to make up
     */
     //{2,5,7} //27
    public int coinChange(int[] A, int M) {
        // write your code here
        int[] f = new int[M+1];
        int n = A.length;
        f[0]=0;
        int i,j;
        for(i=1;i<=M;++i){
            f[i]=Integer.MAX_VALUE;
            for(j=0;j<n;++j){
                if(i>=A[j]&&f[i-A[j]]!=Integer.MAX_VALUE){
                    f[i] = Math.min(f[i-A[j]]+1,f[i]);
                }
            }
        }
        if(f[M] == Integer.MAX_VALUE){
            f[M] = -1;
        }
        return f[M];
    }
}

5.29：补充一下今天在刷Leetcode的第5题 最长回文子串 回想起动态规划最擅长解决带最的问题
感觉通过这几天练习算法有了一些变化，目前给出问题能联想到大概是用什么算法解决，但是具体实现起来又不太会，看一这道题的动态规划代码也不是很懂，只能复制到idea里慢慢DeBug看变量的情况
废话不多说：这道题有三种解决方式1、暴力 2、滑动窗口 3、动态规划
使用的动态规划其实就是滑动窗口优化得来的
上代码：

package LeetCode;

public class L5 {
    public static void main(String[] args) {
        String str = "vcambacv";
        longestStr(str);
    }
    public static void longestStr(String str){
        if (str==null||str.length()<2){
            return;
        }
        int strlength = str.length();
        boolean[][] bp = new boolean[strlength][strlength];
        int start = 0;
        int end = 0;
        int maxlen = 1;
        for (int i = 1; i < strlength; i++) {
            for (int j = 0; j < i; j++) {
                if (str.charAt(i)==str.charAt(j)&&(i-j<=2||bp[i-1][j+1])){
                    bp[i][j] = true;
                    if (i-j+1>maxlen){
                    maxlen = i-j+1;
                    start = j;
                    end = i;
                }
                }
            }
        }
        System.out.println(str.substring(start,end+1));
    }
}

运行结果：v