每日一道算法题拿金币（蓝桥杯练习系统）简单的dp算法-创新互联

资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

输入格式
第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。

输出格式
最多能拿金币数量。

样例输入
3
1 3 3
2 2 2
3 1 2

样例输出
11

数据规模和约定
n<=1000

第一种解法：先创建两个数组，nn数组用来记录每个方格的数，dp用来记录每个位置的最佳选择

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[][] nn=new int[n+1][n+1];
        int[][] dp=new int[n+1][n+1];
        for(int i=0;ifor(int j=0;jnn[i][j]=in.nextInt();
            }
        }
        for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){//左上角的点
                if(i==0&&j==0)
                    dp[i][j]=nn[0][0];
            //如果是第一行，只能是来自左边的点
                else if(i==0){dp[i][j]=dp[i][j-1]+nn[i][j];
           //如果是第一列，只能是来自上面的点
                }else if(j==0){dp[i][j]=dp[i-1][j]+nn[i][j];
           //其余的就选择是来自上面的还是来自左边的大
                }else {dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])+nn[i][j];
                }

            }
        }
        //最后输出遍历的结果
        System.out.println(dp[n][n]);
    }
}

但是提交之后显示内存超限，因为我开了两个数字，题目的内存限制在256.0MB，但是我的却是300.4MB，仔细思考了下，完全没必要开两个数组，一个dp就足够了

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[][] dp=new int[n+1][n+1];
        for(int i=0;ifor(int j=0;jdp[i][j]=in.nextInt();
            }
        }
        for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){if(i==0&&j==0)
                    dp[i][j]=dp[0][0];
                else if(i==0){dp[i][j]+=dp[i][j-1];
                }else if(j==0){dp[i][j]+=dp[i-1][j];
                }else {dp[i][j]+=Math.max(dp[i][j-1],dp[i-1][j]);
                }

            }
        }
        System.out.println(dp[n][n]);
    }
}

这样就正确了

总结：之前刷题一不会就去网上搜现成的代码，但是每次的结果是看到之后依旧不会，所以我决定以后每次刷题如果不会去看知识点，然后自己再思考。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧