每日一道算法题拿金币（蓝桥杯练习系统）简单的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元起，快前往官网查看详情吧

文章标题：每日一道算法题拿金币（蓝桥杯练习系统）简单的dp算法-创新互联
本文URL：http://6mz.cn/article/dgpepd.html