プログラマ整数三角形

質問する

コード#コード#

cpp

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    for(int i=1;i<triangle.size();i++){
        for(int j=0;j<triangle[i].size();j++){
            if(j==0) triangle[i][j]+=triangle[i-1][j]; 
            else if(j==triangle[i].size()-1) triangle[i][j]+=triangle[i-1][j-1];
            else {
                triangle[i][j]+=max(triangle[i-1][j-1],triangle[i-1][j]);
            }
        }
    }
    answer=*max_element(triangle[triangle.size()-1].begin(),triangle[triangle.size()-1].end());
    return answer;
}

python

def solution(m, n, puddles):
    answer = 0
    dp = [[0]*(m+1) for _ in range(n+1)]
    dp[1][1] = 1
    for x, y in puddles:
        dp[y][x] = -1
    for i in range(1, n+1):
        for j in range(1, m+1):
            if dp[i][j] == -1:
                dp[i][j] = 0
                continue
            if i == j == 1:
                continue
            dp[i][j] = dp[i-1][j]+dp[i][j-1]

    return dp[n][m]%1000000007

に答える

           7

        10 15 

     18 16 15 

   20 25 20 19 

24 30 27 26 24