Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- N, M = map(int, (input().split()))
- coinsmap = []
- dp = [[float("-inf")] * (M + 1) for i in range(N + 1)] # Массив стоимостей монет и массив для ДП должны быть разными.
- # Для удобства сделал его на 1 больше. Так не надо делать отдельный проверки, чтобы не выйти за границы массива.
- dp[0][1] = 0 # Начальное состояние
- for j in range(N):
- coinsmap.append(list(map(int, (input().split()))))
- for i in range(1, N + 1): # Идём от 1 до N включительно
- for j in range(1, M + 1):
- a = dp[i - 1][j]
- b = dp[i][j - 1]
- dp[i][j] = coinsmap[i - 1][j - 1] + max(a, b)
- ans = ""
- i, j = N, M
- while i - 1 != 0 or j - 1 != 0:
- if dp[i][j - 1] > dp[i - 1][j]:
- j -= 1
- ans += "R"
- else:
- i -= 1
- ans += "D"
- print(dp[N][M])
- print(ans[::-1])
Advertisement
Add Comment
Please, Sign In to add comment