动态规划算法基本案例

Dynamic Programing

递归算法复杂度太高 可达O(2^n^) 动态规划可达O(n)

使用数组存放已经遍历过的值 下一次可以直接使用而不需要再次进行遍历

exam1

找出给定整数数组不相邻最大和

思路:

每个值对应一个最优解,每个值对应两种情况,一种是选,则结果是它前面两个数的最优解加上它本身,另外一种是不选,结果是它前面一个元素的最优解.

1562071409803

递归法

public void test(){
        int[] array = {4,1,1,9,1};
        System.out.println(opt(array,0,array.length-1));
    }
    public int opt(int[] diguiArray,int s,int i){
        if(i==0){
            return s+diguiArray[0];
        }
        if(i==1){
            if(diguiArray[0]>diguiArray[1]){
                return opt(diguiArray,s,0);
            }else {
                return s+diguiArray[1];
            }
        }else {
            int a = opt(diguiArray,s+diguiArray[i],i-2);
            int b = opt(diguiArray,s,i-1);
            return Math.max(a,b);
        }
    }

动态规划法

public static void main(String[] args) {
        int[] array = {4,1,1,9,1};
        System.out.println(dp(array,array.length-1));
    }
    public static int dp(int[] array,int m){
        int[] dp = new int[array.length];
        for(int i=0;i<array.length;i++){
            if(i==0){
                dp[i] = array[i];
            }else if(i==1){
                if(dp[i-1]>dp[i]){
                    dp[i] = dp[i-1];
                }
            }else {
                int a = dp[i-2]+array[i];
                int b = dp[i-1];
                dp[i] = Math.max(a,b);
            }
        }
        return dp[m];
    }
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/b3bf778.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!