第112回【JavaScript】最長部分増加列、【部分列】最長減少部分列

2024年2月19日

現在取り組んでいるのは、paiza ラーニング問題集「DPメニュー」になります。

プログラミング入門に最適！初心者でも楽しく学べる動画学習サービス【paizaラーニン

paizaラーニングはプログラミング初心者のための動画学習サービスです。1回3分の分かりやすい動画と演 ...

 https://paiza.jp/works

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

JavaScript をゼロから勉強してみよう、のコーナー 112 回目です。

LeoSaki（旦那）が普段やっている業務で、慣れているから何気なくやっていることが、他者から見るととても難しいことに思えることがあるそうです。そんなに尊敬のまなざしで見られても何も出ないですよ・・・。

それでは、今日も頑張ってみようと思います。

最長部分増加列 (paizaランク B 相当)

最長部分増加列 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング

問題を解いてスキルアップ！みんなも一緒に解いてみよう！

 https://paiza.jp/works/mondai/dp_primer/dp_primer_lis_step0

dp[1] <- 1

for i = 2 to n
    dp[i] <- 1  // 木 i のみからなる部分列の長さ
    for j = 1 to i-1
        if a[j] < a[i] then
            dp[i] <- max(dp[i], dp[j]+1)    // 最後が木 j であるような増加部分列の末尾に木 i をくっつける

print max({dp[1], ... ,dp[n]})

n
a_1
a_2
...
a_n

5
100
102
101
91
199

3

これも知っていないと難しい問題ですが、理解すると面白い問題だと思います。

JavaScript

process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
    const n = Number(lines[0]);
    const a = [];
    for (let i = 1; i <= n; i++) {
        a.push(Number(lines[i]));
    }
    const dp = Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (a[j] < a[i]) dp[i] = Math.max(dp[i],dp[j] + 1);
        }
    }
    const max = dp.reduce((a,b) => Math.max(a,b));
    console.log(max);
});

Python

n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1] * n
for i in range(1,n):
    for j in range(0,i):
        if A[j] < A[i]:
            dp[i] = max(dp[i],dp[j]+1)
print(max(dp))

【部分列】最長減少部分列 (paizaランク B 相当)

【部分列】最長減少部分列 | レベルアップ問題集 | プログラミング学習サイト【paiza

問題を解いてスキルアップ！みんなも一緒に解いてみよう！

 https://paiza.jp/works/mondai/dp_primer/dp_primer_lis_boss

n
a_1
a_2
...
a_n

5
109
110
108
103
100

4

前問とは逆のパターン。ちゃんと手打ちでコードを書いてみた方が力になると思う。

JavaScript

process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
    const n = Number(lines[0]);
    const a = [];
    for (let i = 1; i <= n; i++) {
        a.push(Number(lines[i]));
    }
    const dp = Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (a[j] > a[i]) dp[i] = Math.max(dp[i],dp[j]+1);
        }
    }
    const max = dp.reduce((a,b) => Math.max(a,b));
    console.log(max);
});

Python

n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1] * n
for i in range(1,n):
    for j in range(0,i):
        if A[j] > A[i]:
            dp[i] = max(dp[i],dp[j]+1)
print(max(dp))

最後に

なんでこうなるんだろう、と思われた方は、是非、紙に書いてみることをオススメします。多分、理解するための一番の近道だと思うから。

DP 問題はとても好きです。解いていて面白い。人間が頭の中で同じ計算をしようとしても絶対に出来ない（いや、世の中には出来る人がいるんでしょうけれど）気がします。

引き続き、よろしくお願いいたします！

Python の第112回はこちら

第112回【Python】最長部分増加列、【部分列】最長減少部分列

現在取り組んでいるのは、paiza ラーニング問題集「DP メニュー」になります。 paiza ラーニング はじ ...

 https://luna-leo.com/2023/08/10/post-2479/