动态规划&贪心算法

动态规划问题，问题可以分为子问题的最优解，从而递归下去。也可以自下而上的循环来解决，就是找到递归的终点，从递归的终点向上。

package jzof_ex;

public class Jzof_14 {

    public int maxProductCut(int length) {
        if(length<2) {
            return 0;
        }
        if(length==2) {
            return 1;
        }
        if(length==3) {
            return 2;
        }
        int[] product=new int[length+1];
        product[0]=0;
        product[1]=1;
        product[2]=2;
        product[3]=3;
        int max=0;
        for(int i=4;i<=length;i++) {
            max=0;
            for(int j=1;j<=i/2;j++) {
                int temp=product[j]*product[i-j];
                if(max<temp) {
                    max=temp;
                }
            }
            product[i]=max;
        }
        return product[length];
    }
}

矩阵取数的问题
一个N*N的矩阵，要找到路径和最大的，只能向下或者向右走

package jzof_ex;
import java.util.*;
/*
 * 矩阵取数，使得路径的和最大，只能向下或者向右走
 * 20
142 59 82 68 134 88 43 39 134 142 180 29 85 77 189 35 98 98 145 68
61 19 7 136 48 150 99 20 171 68 190 157 117 4 40 73 162 30 80 90
120 186 122 135 192 70 127 48 74 75 23 20 27 174 75 124 52 146 20 183
189 23 67 67 152 23 112 82 38 117 72 68 18 56 148 75 96 71 144 177
24 51 146 97 46 170 131 142 129 115 21 17 11 96 101 98 120 56 183 169
158 46 11 156 3 154 2 170 27 199 29 180 3 43 160 138 76 170 22 181
92 169 152 122 96 56 58 122 155 50 155 40 88 174 20 177 40 189 94 91
168 160 115 129 87 40 15 167 135 162 22 150 35 2 77 188 93 89 60 147
97 80 15 176 45 188 93 28 24 182 98 87 76 130 14 132 55 23 35 57
42 90 186 193 29 6 6 86 98 31 85 151 129 147 193 88 145 138 85 99
147 186 144 152 65 134 74 104 188 145 134 70 54 4 105 8 93 22 148 39
182 7 130 192 98 146 157 129 137 125 186 116 138 136 109 55 145 35 129 94
131 102 97 152 97 16 98 125 42 186 195 123 190 46 116 140 57 152 55 118
177 145 167 64 159 18 132 117 95 50 62 59 93 54 108 81 109 178 96 83
49 32 87 150 129 63 126 92 21 168 198 193 180 11 117 186 134 34 193 80
83 181 31 191 125 137 31 136 138 35 31 79 56 172 70 145 58 18 134 96
91 40 96 126 52 68 79 83 137 122 147 76 185 17 199 67 2 96 25 192
33 189 154 185 138 120 137 9 141 171 128 117 99 97 188 43 85 105 140 57
59 148 199 17 88 155 94 40 172 3 144 162 192 141 63 101 86 111 188 131
130 70 141 165 193 30 176 88 28 156 182 97 155 168 134 85 190 137 98 182
5559
 */
public class GetNumOfMatrix {

    //递归的实现，矩阵小的时候还可以，20*20的似乎就跑不了了
    public int maxPath(int[][] arr,int i,int j) {
        if(i==0|j==0) {
            if(i==0&&j!=0) {
                return maxPath(arr,0,j-1)+arr[0][j];
            }else if(i!=0&&j==0) {
                return maxPath(arr,i-1,0)+arr[i][0];
            }else{
                return arr[0][0];
            }
        }else {
            return Math.max(maxPath(arr,i-1,j),maxPath(arr,i,j-1))+arr[i][j];
        }
    }
    
    //非递归的实现，其实就是中间结果有存储起来，递归太深了
    //可以考虑下具体是怎样的，当要找到这条路径的时候
    public static void main(String[] args) {
        // TODO 自动生成的方法存根

        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int[][] arr=new int[N][N];
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                arr[i][j]=sc.nextInt();
            }
        }
        int[][] sum=new int[N][N];
        sc.close();
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(i!=0&&j!=0) {
                    if(sum[i-1][j]>sum[i][j-1]) {
                        sum[i][j]=sum[i-1][j]+arr[i][j];
                    }else {
                        sum[i][j]=sum[i][j-1]+arr[i][j];
                    }
                }else {
                    if(i==0&&j!=0) {
                        sum[i][j]=sum[i][j-1]+arr[i][j];
                    }else if(i!=0&&j==0) {
                        sum[i][j]=sum[i-1][j]+arr[i][j];
                    }else {
                        sum[i][j]=arr[i][j];
                    }
                }
            }
        }
        System.out.println(sum[N-1][N-1]%2147483647);
    }

}